# Iteration

AbstractTrees.jl provides algorithms for iterating through the nodes of trees in certain ways.

## Interface

Iterators can be constructed for any tree that implements The Abstract Tree Interface with a 1-argument constructor on the root. For example `collect(Leaves(node))`

returns a `Vector`

containing the leaves of the tree of which `node`

is the root.

Trees can define additional methods to simplify the iteration procedure. To guarantee to the compiler that all nodes connected to a node of type `ExampleNode`

are of the same type

```
Base.IteratorEltype(::Type{<:TreeIterator{ExampleNode}}) = Base.HasEltype()
Base.eltype(::Type{<:TreeIterator{ExampleNode}}) = ExampleNode
```

While AbstractTrees.jl does its best to infer types appropriately, it is usually not possible to determine the types involved in iteration over a general tree. For performance critical trees it is crucial to define `Base.IteratorEltype`

and `Base.eltype`

for `TreeIterator`

.

## Iterators

All iterators provided by AbstractTrees.jl are of the `TreeIterator`

abstract type.

`AbstractTrees.TreeIterator`

— Type`TreeIterator{T}`

An iterator of a tree that implements the AbstractTrees interface. Every `TreeIterator`

is simply a wrapper of an `IteratorState`

which fully determine the iteration state and implement their own alternative protocol using `next`

.

**Constructors**

All `TreeIterator`

s have a one argument constructor `T(node)`

which starts iteration from `node`

.

`AbstractTrees.PreOrderDFS`

— Type`PreOrderDFS{T,F} <: TreeIterator{T}`

Iterator to visit the nodes of a tree, guaranteeing that parents will be visited before their children.

Optionally takes a filter function that determines whether the iterator should continue iterating over a node's children (if it has any) or should consider that node a leaf.

e.g. for the tree

```
Any[Any[1,2],Any[3,4]]
├─ Any[1,2]
| ├─ 1
| └─ 2
└─ Any[3,4]
├─ 3
└─ 4
```

we will get `[[[1, 2], [3, 4]], [1, 2], 1, 2, [3, 4], 3, 4]`

.

`AbstractTrees.PostOrderDFS`

— Type`PostOrderDFS{T} <: TreeIterator{T}`

Iterator to visit the nodes of a tree, guaranteeing that children will be visited before their parents.

e.g. for the tree

```
Any[1,Any[2,3]]
├─ 1
└─ Any[2,3]
├─ 2
└─ 3
```

we will get `[1, 2, 3, [2, 3], [1, [2, 3]]]`

.

`AbstractTrees.Leaves`

— Type`Leaves{T} <: TreeIterator{T}`

Iterator to visit the leaves of a tree, e.g. for the tree

```
Any[1,Any[2,3]]
├─ 1
└─ Any[2,3]
├─ 2
└─ 3
```

we will get `[1,2,3]`

.

`AbstractTrees.Siblings`

— Type`Siblings{T} <: TreeIterator{T}`

A `TreeIterator`

which visits the siblings of a node after the provided node.

`AbstractTrees.StatelessBFS`

— Type`StatelessBFS{T} <: TreeIterator{T}`

Iterator to visit the nodes of a tree, all nodes of a level will be visited before their children

This iterator requires `getdescendant`

to be valid for all nodes in the tree, but the nodes do not necessarily need the `IndexedChildren`

trait.

e.g. for the tree

```
Any[1,Any[2,3]]
├─ 1
└─ Any[2,3]
├─ 2
└─ 3
```

we will get `[[1, [2,3]], 1, [2, 3], 2, 3]`

.

WARNING: This is $O(n^2)$, only use this if you know you need it, as opposed to a more standard stateful approach.

`AbstractTrees.treemap`

— Function`treemap(f, node)`

Apply the function `f`

to every node in the tree with root `node`

, where `f`

is a function that returns `(v, ch)`

where `v`

is a new value for the node (i.e. as returned by `nodevalue`

and `ch`

is the new children of the node. `f`

will be called recursively so that all the children returned by `f`

for a parent node will again be called for each child. This means that to maintain the structure of a tree but merely map to new values, one should define `f = node -> (g(node), children(node))`

for some function `g`

which returns a value for the node.

The nodes of the output tree will all be represented by `MapNode`

objects wrapping the returned values. This is necessary in order to guarantee that the output types can describe any tree topology.

Note that in most common cases tree nodes are of a type which depends on their connectedness and the function `f`

should take this into account. For example the tree `[1, [2, 3]]`

contains integer leaves but two `Vector`

nodes. Therefore, the `f`

in `treemap(f, [1, [2,3]])`

must be a function that is valid for either `Int`

or `Vector`

. Alternatively, to only operate on leaves do `map(𝒻, Leaves(itr))`

.

It's very easy to write an `f`

that makes `treemap`

stack-overflow. To avoid this, ensure that `f`

eventually terminates, i.e. that sometimes it returns empty `children`

. For example, if `f(n) = (nothing, [0; children(n)])`

will stack-overflow because every node will have at least 1 child.

To create a tree with `HasNodeType`

which enables efficient iteration, see `StableNode`

instead.

**Examples**

```
julia> t = [1, [2, 3]];
julia> f(n) = n isa AbstractArray ? (nothing, children(n)) : (n+1, children(n))
julia> treemap(f, t)
nothing
├─ 2
└─ nothing
├─ 3
└─ 4
julia> g(n) = isempty(children(n)) ? (nodevalue(n), []) : (nodevalue(n), [0; children(n)])
g (generic function with 1 method)
julia> treemap(g, t)
Any[1, [2, 3]]
├─ 0
├─ 1
└─ [2, 3]
├─ 0
├─ 2
└─ 3
```

### Iterator States

Any iterator with a state (that is, all except `StatelessBFS`

) are wrappers around objects which by themselves contain all information needed for iteration. Such a state defines an alternative iteration protocol which can be iterated through by calling `next(s)`

.

`AbstractTrees.IteratorState`

— Type`IteratorState{T<:TreeCursor}`

The state of a `TreeIterator`

object. These are simple wrappers of `TreeCursor`

objects which define a method for `next`

. `TreeIterator`

s are in turn simple wrappers of `IteratorState`

s.

Each `IteratorState`

fully determines the current iteration state and therefore the next state can be obtained with `next`

(`nothing`

is returned after the final state is reached).

`AbstractTrees.PreOrderState`

— Type`PreOrderState{T<:TreeCursor} <: IteratorState{T}`

The iteration state of a tree iterator which guarantees that parent nodes will be visited *before* their children, i.e. which descends a tree from root to leaves.

This state implements a `next`

method which accepts a filter function as its first argument, allowing tree branches to be skipped.

See `PreOrderDFS`

.

`AbstractTrees.PostOrderState`

— Type`PostOrderState{T<:TreeCursor} <: IteratorState{T}`

The state of a tree iterator which guarantees that parents are visited *after* their children, i.e. ascends a tree from leaves to root.

See `PostOrderDFS`

.

`AbstractTrees.LeavesState`

— Type`LeavesState{T<:TreeCursor} <: IteratorState{T}`

A `IteratorState`

of an iterator which visits the leaves of a tree.

See `Leaves`

.

`AbstractTrees.SiblingState`

— Type`SiblingState{T<:TreeCursor} <: IteratorState{T}`

A `IteratorState`

of an iterator which visits all of the tree siblings after the current sibling.

See `Siblings`

.

`IteratorState`

Functions

`AbstractTrees.instance`

— Function`instance(::Type{<:IteratorState}, node; kw...)`

Create an instance of the given `IteratorState`

around node `node`

. This is mostly just a constructor for `IteratorState`

except that if `node`

is `nothing`

it will return `nothing`

.

`AbstractTrees.initial`

— Function`initial(::Type{<:IteratorState}, node)`

Obtain the initial `IteratorState`

of the provided type for the node `node`

.

`AbstractTrees.next`

— Function```
next(s::IteratorState)
next(f, s::IteratorState)
```

Obtain the next `IteratorState`

after the current one. If `s`

is the final state, this will return `nothing`

.

This provides an alternative iteration protocol which only uses the states directly as opposed to `Base.iterate`

which takes an iterator object and the current state as separate arguments.

`AbstractTrees.statetype`

— Function`statetype(::Type{<:TreeIterator})`

Gives the type of `IteratorState`

which is the state of the provided `TreeIterator`

.