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?!