All in order

I swear I have rare moments of clarity. I was really happy when I finally realized how a non-recursive in-order binary tree traversal would work. It’s a piece of CS trivia that I continually forget. I’m also pleased to realize how easy it is to write in python as an iterator class. 16 lines, with comments and some white space.

class _OrderIterator:
    """An in-order traversal iterator."""
    def __init__(self, head):
        self._stack = [head]

    def next(self):
        cur = self._stack.pop()
        while cur:
            self._stack.append(cur)
            cur = cur.left

        if not len(self._stack):
            raise StopIteration
        cur = self._stack.pop()

        self._stack.append(cur.right)
        return cur.value

Now that you see it, isn’t it just freaking obvious?!