Non-allocating leaf iterator over simple tree

General Usage Performance
1

I have a tree made from a node type like this

struct Node
    children::Vector{Node}
end

For the life of me, I cannot figure out how to write a non-allocating iterator over the leaves of that tree.

I tried with generators, but it’s hard to get those type stable in something like this, because ideally both branches would return the same type of iterator.

function leaves(t::Node)
    Iterators.flatten(isempty(c.children) ? (c for _ in 1:1) : leaves(c) for c in t.children)
end

Another option was ResumableFunctions:

ResumableFunctions.@resumable function leaves(t::Node)
    for c in t.children
        if isempty(c.children)
            @yield c
        else
            for leaf in leaves(c)
                @yield leaf
            end
        end
    end
end

Both of these allocate. I tried AbstractTrees but even with defining a bunch of the methods listed in the docs, it’s still allocating a lot.

AbstractTrees.children(t::Node) = t.children
AbstractTrees.childrentype(::Type{Node{<:T}}) where T = Vector{Node{T}}
Base.IteratorEltype(::Type{<:AbstractTrees.TreeIterator{<:Node}}) = Base.HasEltype()
Base.eltype(::Type{<:AbstractTrees.TreeIterator{<:T}}) where T <: Node = T