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.)

or, in Python 3.3:

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

Very nice. That would solve the basic inefficiency.

Exactly right. Part two will be about generators like this, as well as coroutines and fibers. Simple generators don't really let you flip internal and external iteration, they just give you a nice way to reify a single stack frame. Coroutines and fibers are even more awesome because they let you reify an entire callstack.

Of course the downside of that kind of power is that it makes it very hard to reason about what code will do sometimes. As I once heard about continuations, it is a like a goroutine, only worse.