Generator behaviour

[bla123bla]

Hello,

encountered this smart piece of breadth-first traversal:

def bfs(root):
    yield root
    for n in bfs(root):
        yield n.left
        yield n.right

but am confused about pythons behaviour here.

If you omit the first yield, the (recursive?) generator call on line 3 is
empty and this results in endless recursion, so behaves like a function
call. (One would expect it to not get executed at all).

But with the first yield, the non-empty generator gets iterated over.
Looks like the call behaves like a function in one case and a generator in
the other?

[deanhystad]

I cannot get the code to work. When I call bcs() it traverses the tree level by level, but eventually left or right will be None, and that results in trying to get None.left and None.right. If I only yield left and right in n is not None, that fixes the attribute error, but then it hits the recursion limit. Maybe I am making the wrong kind of tree.

If you remove "yield root", bcs() cannot yield a result. There is no way to get past the internal bcs(root) call to yield n.left or yield n.right. bcs(root) calls bcs(root) which calls bcs(root) and nothing is ever generated.

[bla123bla]

Hi, thanks. Just wanted to discuss the code a bit.
This looks deceptively simply, but is quite nifty.

Normally, bfs is done with a queue.
But, can bfs done with pure recursion?
If you don't count the state inherent in generators,
this demonstrates it.

Drawback of this solution is suboptimal complexity.

Has anyone else wrapped their head around it?