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.
Your above method would become
def __iter__(self):
return chain(self._left, [self._value], self._right)
i. e. you wrap the value in an iterable.
But I don't see how this could help in terms of big O.
> 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
--
https://mail.python.org/mailman/listinfo/python-list
