A pre-order Iterator

class PreOrderIterator implements Iterator
{
  public PreOrderIterator(Tree tree) {
    stack_.push(tree.root());
  }

  public boolean hasNext() {
    return !stack_.empty();
  }

  public Object next(){
    Node next = (Node)stack_.pop();
    if(next.left != null)
      stack_.push(next.left);
    if(next.right != null)
      stack_.push(next.right);
    return next;
  }

  public void remove() { ... }

  private Stack stack_ = new Stack();
}
Here's a nice preorder iterator. Postorder is little trickier - you can use a stack again, but you need to keep track of how many times you've need to push stuff back on the stack and keep track of the count, or you maintain a dual stack. Alternatively, you can keep a little bit of state and use the iterator class as part of it's own implementation.

Trees aren't super-common in the wild, as naked trees anyway. Parent-child relationships are common, though. Files and directories, maybe? XML is used a lot, and that's a often represented as a tree - an annotated tree even, because elements can have attributes but the attributes aren't part of the tree proper. Acyclic graphs? Other structures? Different traversal strategies - depth first, breadth-first, depth-limit? There are any number of data structures which have no obvious "natural" interation order.

In fact, if our tree does represent an XML document then XPath defines (depending on quite how you count it) 9 different ways to walk the tree.

By externalising the tree iteration we've not only done that classical computer science thing - abstracting away from the implementation of the container - we're also abstracting away from the iteration order.

Why is this a useful thing to do?

Well, once we have an iterator we can work with it in an entirely normal and unexciting way. This is a good thing, because it means we can concentrate on the processing and not the details of the how we walk the container.

Helpfully, iterators are usually quite easy to write, even for "tricky data structures". Take this as an example. I wrote this, the in order and post order counterparts from scratch, with tests, in about 10 minutes.

(Which leads me on to a related point (which I'm not going to labour particularly). Iterators are pretty easy to test.)

Iterators are certainly easier to write than a collection. Here's what Java expects from a collection