On Tuesday, September 20, 2016 at 12:48:55 PM UTC-4, 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?
Another option is linear time, log-n space, by using an explicit stack
in your iterator:
def __iter__(self):
cur = self
stack = []
while True:
if cur:
stack.append(cur)
cur = cur._left
elif not stack:
break
else:
cur = stack.pop()
yield cur._value
cur = cur._right
This replaces the Python call stack with a list variable which tracks
parent nodes we haven't yet iterated, so it will grow as log-n. There's
no Python recursion, so each yield directly produces a value to the
caller.
--Ned.
--
https://mail.python.org/mailman/listinfo/python-list
