Do we create n iterators when we use yield recursively?

Question

Consider:

def iterInOrder(node):
    if node.left:
        for n in iterInOrder(node.left):
            yield n
    yield node
    if node.right:
        for n in iterInOrder(node.right):
            yield n

And let n be number of nodes in the input binary tree, Do we create a single generator that yields n nodes? Or do we create n iterators that each generate a node? what can you say about space/time complexity of that code comparing to a simple recursive travel:

def visitInOrder(node):
    if node.left:
        visitInOrder(node.left)
    visit(node)
    if node.right:
        visitInOrder(node.right)

I care more for Python 2, but may be nice to know if answer differs for Python 3.

You create `n` generators, each of which yields anywhere between 1 node (for the leaf nodes) and `n` nodes (for the root node). If you weren't stuck with Python 2.x, you could make the code a bit more concise by using `yield from` instead of explicitly iterating over the sub-generators, but I don't think that changes the complexity at all. — jasonharper, Nov 04 '20 at 18:04
similar or duplicate: https://stackoverflow.com/questions/61591596/does-yield-from-have-o1-time-complexity — shx2, Nov 04 '20 at 18:27

score 3 · Answer 1 · answered Nov 04 '20 at 18:17

In CPython, each call to iterInOrder() creates a new generator-iterator, regardless of Python version, and regardless of whether it's a top-level or recursive call.

Similarly, each call to visitInOrder() creates a new stack frame, again regardless of Python version or context.

So the space complexity is O(depth(tree)) either way (which doesn't have a useful relation, in general, to the number of nodes - the tree may be n levels deeps, or 2 levels deep).

Time is a different calculation, but subtle because it's barely ever noticeable: the recursive version has O(n) time complexity, but that's a lower bound on the generator version. Each time you yield, the yielded value is passed up the chain of recursive generator calls, one level at a time, until it's finally consumed by the top-level call. Then, when the chain is resumed, the stack of generator-iterator frames is reactivated one at a time, until getting back down to the original yield.

So in the generator version there is a time component quadratic in depth(tree). But unless the tree is very deep, you'll probably never notice that, because in CPython all that stack unwinding and rewinding occurs "at C speed".

For a binary tree (which the code implies is being used here), the smallest possible maximum depth is `ceil(log2(n))`. But otherwise this is a fantastic analysis! — Blckknght, Nov 04 '20 at 18:59
Ah, thanks @Blckknght - I indeed overlooked the "binary" part. — Tim Peters, Nov 04 '20 at 19:04

Do we create n iterators when we use yield recursively?

1 Answers1