Linear Time Tree Traversal Generator

[Random832]

On Tue, Sep 20, 2016, at 22:34, Steve D'Aprano wrote:
> I'm afraid I don't understand this. This is a standard binary tree
> inorder traversal. Each node is visited once, and there are N nodes,
> so I make that out to be O(N) not O(N log N). I'm afraid I can't parse
> your final clause:
>
>     "since values from the leaves of the tree have to be yielded
>     multiple times to the top of the tree"
>
> Each leaf is yielded once, and I don't understand what you mean by
> yielding to the top of the tree.

His point is that in order for the top-level iterator to return a given
node there's a yield call in the top level's iterator , that calls the
next level's iterator's yield, that calls the next one, so on, in a call
stack log(n) levels deep.