Linear Time Tree Traversal Generator

[Steve D'Aprano]

On Wed, 21 Sep 2016 02:46 am, ROGER GRAYDON CHRISTMAN wrote:

> I am trying to find a better (i.e. more efficient) way to implement a
> generator that traverses a tree.
> 
> The current model of the code (which is also used by a textbook I am
> teaching from does this)
> 
>    def __iter__(node):
>          for x in iter(node._left):
>               yield x
>          yield node._value
>          for x in iter(node._right)
>               yield x
> 
> This is nice, simple, and straightforward, but has an O(n log n) running
> time, since
> values from the leaves of the tree have to be yielded multiple times to
> the top of the tree.
> 
> Now, I could certainly implement a linear-time traversal without the
> gnerator:
> 
>     def to_list(node,result):
>           """append node information to result"""
>           result = to_list(node._left, result)
>           result.append(node._value)
>           return to_list(node,_right, result)


I forgot to ask... 

How to you reason that this is O(N) time if the same algorithm above is
supposedly O(N log N)? They're both the same algorithm, with the same
performance characteristics. They differ only that the __iter__ version
yields the items one at a time, while the to_list version accumulates them
into a list all at once. But they walk the tree in the same way, touch the
same number of nodes, generate the same depth of calling stack.

You can re-write to_list as:

def to_list(node):
    result = []
    for value in node:  # calls __iter__ method above
        result.append(node)
    return result



One of us is badly missing something.




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