Linear Time Tree Traversal Generator

[Chris Angelico]

On Wed, Sep 21, 2016 at 2:46 AM, ROGER GRAYDON CHRISTMAN <dvl at psu.edu> wrote:
> 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.
>

Normally I'd implement it thus:

def __iter__(self):
    if self._left: yield from self._left
    yield self._value
    if self._right: yield from self._right

But as far as I can see, it's equivalent to your code, except that I
allow the left and right nodes to be None (you might have something
iterable-but-empty in leaf nodes - not sure).

The 'yield from' operation is highly optimized, so it's not going to
cost too much. You don't have to concern yourself overly with the
"yielding up the chain" cost here, as it'll all be done for you by the
interpreter. It's entirely possible for the interpreter to actually
eliminate the chain by storing a reference to the deepest generator;
in any case, it's adequately fast for everything I've ever needed of
it.

ChrisA