# Recursive Iterators (or some other way to do this)

Hi, I am experimenting with some custom iterators, and I’m wondering why this particular construction does not work as I would think (it returns nothing):

``````struct TreeNodeLeaves{T <: TreeNode}
node::T
end

function iterate(leaves::TreeNodeLeaves, state::Tuple{Vector{BranchNode}, Vector{Int}})
function transverse(substate::Tuple{Vector{BranchNode}, Vector{Int}})
if length(substate) == 0
return nothing
end
current = pop!(substate)

if length(current.children) == 0
return ((current.data, copy(substate)), substate)
end
for index = eachindex(current.children)
nextnode = current.children[index]
push!(substate, nextnode)
push!(substate, index)
transverse(substate)
pop!(substate)
end
end
return transverse(state)
end

function iterate(leaves::TreeNodeLeaves)
nodes = Vector{BranchNode}()
indices = Int[]

push!(nodes, leaves.node)

return iterate(leaves, (nodes, indices))
end
``````

The expected output is to return something like `("a", [2, 2, 1, 2, 2])` from each iteration (where the integer array is the path to get to that node) until I’ve traversed the entire tree. If iterators are not the way to go with this, is there something else I can do such that I can iterate over something and get this type of return value with each iteration?

Hi

This is difficult to debug without the rest of the code to make it a minimal working example (missing definitions of TreeNode, BranchNode and TreeNodeLeaves as well as example input).

However if I assume you are calling:
`iterate(leaves)`
which then calls
`iterate(leaves, ( Vector{BranchNode}(), Int[]) )`
that in turn calls
`transverse( ( Vector{BranchNode}(), Int[]) )`
which finds a `length(substate)` which is `Vector{BranchNode}()` is `0`, and returns the `nothing`

I only partially understand your logic based on a quick scan.
My first guess was your check is the wrong way around (should check for not equal to 0), however that doesn’t make sense. Even removing the if length substate check also wouldn’t work, since you need to check that there is stuff to pop.

I think on this line there might be a problem:
`push!(substate, index)`
I think you need to also be pushing a copy of the path (substate) to get to current, not just the last step, but I might be wrong.

But I think the real problem is the setup in the first call, which needs to be calling with the root element of the tree already populated in nodes, instead of an empty vector.

yeah - I wasn’t able to really get it working with an iterator, but using channels I get my desired output:

``````    code = Int[]
function traverse(node::TreeNode, c::Channel)
if node == nullnode
return
end
if length(node.children) == 0
put!(c, (node.data, copy(code)))    # notice that we should copy the current state of code
end
for index = eachindex(node.children)
child = node.children[index]
push!(code, index)
traverse(child, c)
pop!(code)
end
end
return Channel((channel_arg) -> traverse(root, channel_arg))
end
``````

I was trying to update this little package: https://github.com/tanmaykm/Word2Vec.jl to work in 1.0/1.1, but the author was using Tasks (with produce/consume etc) which is obviously long deprecated.