Iteration Inside and Out

If you've got iterators and a yield statement, like Python does, you can make the tree example look much nicer:

  def in_order (self):
      if self.left is not None:
          for node in self.left.in_order():
              yield node
      yield self.node
      if self.right is not None:
          for node in self.right.in_order():
              yield node

Unfortunately this is horribly inefficient if the tree has deep nodes because each iterator call recursively calls each level of the tree, only do just pass values back. If there was something like tail call optimization for iterators in Python, then this could actually be efficient. But there is not.

However it does show that, at least in principle, the external form of iteration can make the tree problem look pretty.

(Purists can claim with justice that that I'm cheating. The yield primitive allows co-routines to be constructed, which allows you to effectively flip internal and external. That is why it was one of the solutions to allow internal iterators to solve the interleaving problem.)