Linear Time Tree Traversal Generator
Random832
random832 at fastmail.com
Wed Sep 21 13:15:53 EDT 2016
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
More information about the Python-list
mailing list