Linear Time Tree Traversal Generator
Random832
random832 at fastmail.com
Tue Sep 20 22:44:01 EDT 2016
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.
More information about the Python-list
mailing list