9.3.1. General design concerns for a tree iterator

We now consider the problem of returning the elements of a tree one by one, using an iterator. To do this, we will implement the interface java.util.Iterator<TreeNode<Item>>, which prescribes three methods:

    /** True iff there are more tree elements yet to be returned. */
    boolean hasNext ( );

    /** The label on the next tree in this iteration sequence. 
     *  Precondition: hasNext ( ); throws NoSuchElementException when 
     *   that precondition is not met. */
    TreeNode<Item> next ( );

    /** Remove the node of the last label returned by next.  Not
     *  supported by our trees. */
    void remove ( );
We will use an inner iterator class to hide the details of the enumeration.

As in previous iterators, we need to maintain state saving information that lets us find the next tree element to return, and we now must determine what that information might include. To help work this out, we'll consider the sample tree below, with elements to be returned depth first as indicated by the numbers.

The first element to be returned is the one labeled "1". Once that's done, we need to somewhere keep track of the fact that we have to return at some point to element "5". Similarly, once we return element "2", we have to remember that element "4" is yet to return, as in the diagram below.

That means that our state-saving information must include not just a single pointer of what to return next, but a whole collection of "bookmarks" to nodes we've passed along the way.

More generally, we will maintain a collection that we'll call fringe or frontier of all the nodes in the tree that are candidates for returning next. The next method will choose one of the elements of the fringe as the one to return, then add its children to the fringe as candidates for the next element to return. hasNext is true when the fringe isn't empty.

The iteration sequence will then depend on the order we take nodes out of the fringe. Depth-first iteration, for example, results from storing the fringe elements in a stack, a last-in first-out structure. The java.util class library conveniently contains a Stack class with push and pop methods. We illustrate this process on a binary tree in which tree nodes have 0, 1, or 2 children named left and right. Here is the code (an inner class nested inside BinaryTree). It is also in ~cs61b/code/lab9/BinaryTree.java.

public class DepthFirstIterator implements Iterator<TreeNode<Item>> {

    private Stack<TreeNode<Item>> fringe = new Stack<TreeNode<Item>> ( );

    public DepthFirstIterator ( ) {
	// Java fact.  Since DepthFirstIterator is an inner class of
	// BinaryTree, and has no "myRoot" member itself, 
	// "myRoot" here is shorthand for "BinaryTree.this.myRoot".
        if (myRoot != null) {
            fringe.push (myRoot);
        }
    }

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

    public TreeNode<Item> next ( ) {
        if (!hasNext ( )) {
            throw new NoSuchElementException ("tree ran out of elements");
        }
        TreeNode<Item> node = fringe.pop ( );
        if (node.right != null) {
            fringe.push (node.right);
        }
        if (node.left != null) {
            fringe.push (node.left);
        }
        return node;
    }

    public void remove () {
        throw new UnsupportedOperationException ();
    }
}