Linear Time Tree Traversal Generator

[Random832]

On Tue, Sep 20, 2016, at 23:34, Steve D'Aprano wrote:
> One of us is badly missing something.

The problem is the number of times next is called. Here, it'll be more
clear if we wrap the iterator in the original example to print each time
next is called.

class WrappedIterator():
    def __init__(self, orig, reference):
        self.orig = orig
        self.ref = reference
    def __iter__(self):
        return self
    def __next__(self):
        desc = "next for " + self.ref
        try:
            result = next(self.orig)
            print(desc, '=', result)
            return result
        except StopIteration:
            print(desc, "StopIteration")
            raise

class Node:
    def __init__(self, value, left=None, right=None):
        self._value = value
        self._left = left
        self._right = right
    def _iter(node):
        if node._left:
            for x in iter(node._left):
                yield x
        yield node._value
        if node._right:
            for x in iter(node._right):
                yield x
    def __iter__(self):
        return WrappedIterator(self._iter(), 'Node %r' % self._value)

node1 = Node(1)
node3 = Node(3)
node2 = Node(2, node1, node3)
node5 = Node(5)
node7 = Node(7)
node6 = Node(6, node5, node7)
node4 = Node(4, node2, node6)

for value in node4:
    print("Got value %r" % (value,))

---output---

next for Node 1 = 1
next for Node 2 = 1
next for Node 4 = 1
Got value 1
next for Node 1 StopIteration
next for Node 2 = 2
next for Node 4 = 2
Got value 2
next for Node 3 = 3
next for Node 2 = 3
next for Node 4 = 3
Got value 3
next for Node 3 StopIteration
next for Node 2 StopIteration
next for Node 4 = 4
Got value 4
next for Node 5 = 5
next for Node 6 = 5
next for Node 4 = 5
Got value 5
next for Node 5 StopIteration
next for Node 6 = 6
next for Node 4 = 6
Got value 6
next for Node 7 = 7
next for Node 6 = 7
next for Node 4 = 7
Got value 7
next for Node 7 StopIteration
next for Node 6 StopIteration
next for Node 4 StopIteration

------

You can see that next is called three times (log N) for each value
returned.

It's not about the stack space, it's about going up and down the stack
over and over.