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