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
"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.
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.