Linear Time Tree Traversal Generator

[Steve D'Aprano]

On Wed, 21 Sep 2016 12:44 pm, Random832 wrote:

> 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.

Right. That's the whole point of a binary search tree. An unbalanced binary
tree may be as deep as N, but a balanced one, or a random unbalanced one,
is only log N deep.

log N is a long way from N log N.

I don't see what is the actual problem we are being asked to solve. Is it
the stack space needed to walk the tree? The time taken? The Original
Poster said:

    "O(n log n) running time"

so I don't think the O(log N) stack space used is relevant.


In a practical sense, the right way to solve this problem is to not use a
tree in the first place. But presumably the OP is using this for teaching
about trees, not as production software.




-- 
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.