Linear Time Tree Traversal Generator

[Rob Gaddi]

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

The only thing that's O(N log N) in that is the number of actual yield
calls.  If you're doing pretty much anything with those values as
they're being iterated over then they'll dominate the timing, and that
is O(N).

If you're using Python 3.4 or above you can turn that into

    def __iter__(node):
          yield from iter(node._left)
          yield node._value
          yield from iter(node._right)

I think there's a little bit of optimization that goes on using yield
from.  That said, all this has a serious stink of premature
optimization.

-- 
Rob Gaddi, Highland Technology -- www.highlandtechnology.com
Email address domain is currently out of order.  See above to fix.