Linear Time Tree Traversal Generator

[Random832]

On Wed, Sep 21, 2016, at 10:39, ROGER GRAYDON CHRISTMAN wrote:
> Which only highlights my disappointment that my tree
> traversal itself was O(n log n), unless I gave up on yield.

Or you can give up on recursion. Recursive tree traversal is generally
associated with passing in a callback in rather than implementing an
iterable-like interface that can be used with a caller's for-loop
anyway.

    def __iter__(node):
        stack = []
        while stack or node:
            if node:
                stack.append(node)
                node = node._left
            else:
                node = stack.pop()
                yield node._value
                node = node._right