Linear Time Tree Traversal Generator

[Peter Otten]

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)
> 
> but then that requires the extra memory space to build the list into,
> which is basically what the generator is supposed to avoid.
> 
> Now, I did see that itertools has a chain method for concatenating
> iterators, so it would be nice to concatenate the results from the
> recursive calls without the for loops, but I have no idea how to
> squeeze the 'yield node._value' in between them.

Your above method would become

    def __iter__(self):
        return chain(self._left, [self._value], self._right)

i. e. you wrap the value in an iterable. 

But I don't see how this could help in terms of big O.
 
> Is there hope for a linear-time tree-traversal generator, or will
> I have just have to settle for an n-log-n generator or a linear time
> behavior with linear extra space?
> 
> Roger Christman
> instructor
> Pennsylvania State University