I want to implement Base.iterate so that it can recursively iterate over a tree - it seems to me that gives the best performance.

The type is defined as follows:

```
mutable struct node
next::Union{node,Missing}
first_child::Union{node,Missing}
last_child::Union{node,Missing}
end
```

next points to the next child of the same ancestor (basically a linked list)

first_child points to the first child of a node.

I would like to have Base.iterate implemented such that it returns the nodes in Pre-order (Neutral, Left, Right)

**Quick example:**

```
A
/ | \
B D E
/ / \
C F G
```

Note: A through G are all of type `node`

. B.next is D, because they are both children of A. However C.next is â€śmissingâ€ť; B has no other children.

In a call like

```
for element in A
element
end
```

I would like the output to be A - B - C - D - E - F - G

**My Impressions/Attempts** (you can skip this, if you already know a good answer)

I tried to implement `Base.iterate(elem::node,state)`

with recursive calls to `Base.iterate(elem::node,state)`

in its definition. This would either result in an endless loop or only return the first element.

I tried to use the `Continuables`

package but got the same result.

A problem i suspect is, that the elements returned by the iterator must be returned as `return (element,state)`

in a function with signature` Base.iterate(elem::node, state)`

. That implies however that the function ends at that point; however i would like to do something like:

```
return (elem,state) #first, return the current node
#for all children of elem
Base.iterate(child) #then, return the children and their subtrees
end
```

It seems (to me) that that would be the correct way to enter the subtrees recursively; However the `return`

statement puts an early stop to things (all that would be needed to remedy this situation would be a `return`

statement, that yields the element, but doesnt stop the program.)

**Question 1:** For future reference: How can i implement `Base.iterate`

in a recursive fashion like that? (This question is meant generally, not necessarily involving my specific node implementation here)

**Question 2:** What do you think would be the best/most performant way to implement an iterator for a tree-structure, that returns the elements in Pre-order?