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


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.


All iterators provided by AbstractTrees.jl are of the TreeIterator abstract type.


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.


All TreeIterators have a one argument constructor T(node) which starts iteration from node.

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[1,2]
|  ├─ 1
|  └─ 2
└─ Any[3,4]
   ├─ 3
   └─ 4

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

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

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

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

Leaves{T} <: TreeIterator{T}

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

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

we will get [1,2,3].

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

├─ 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.

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.


julia> t = [1, [2, 3]];

julia> f(n) = n isa AbstractArray ? (nothing, children(n)) : (n+1, children(n))

julia> treemap(f, t)
├─ 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).


The state of a TreeIterator object. These are simple wrappers of TreeCursor objects which define a method for next. TreeIterators are in turn simple wrappers of IteratorStates.

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).

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.

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.

IteratorState Functions

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.

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.