Iterators

BST is iterable because it is defined as a subtype of the java.lang.Iterable interface.

The methods inorder(), preorder(), and postorder() display the elements in inorder, preorder, and postorder in a binary tree. These methods are limited to displaying the elements in a tree. If you wish to process the elements in a binary tree rather than display them, these methods cannot be used. Recall that an iterator is provided for traversing the elements in a set or list. You can apply the same approach in a binary tree to provide a uniform way of traversing the elements in a binary tree.

The java.lang.Iterable interface defines the iterator method, which returns an instance of the java.util.Iterator interface. The java.util.Iterator interface (see Figure below) defines the common features of iterators.

The Tree interface extends java.lang.Iterable. Since BST is a subclass of AbstractTree and AbstractTree implements Tree, BST is a subtype of Iterable. The Iterable interface contains the iterator() method that returns an instance of java.util.Iterator.

You can traverse a binary tree in inorder, preorder, or postorder. Since inorder is used frequently, we will use inorder for traversing the elements in a binary tree. We define an iterator class named InorderIterator to implement the java.util.Iterator interface in BST.java (lines 219–263). The iterator method simply returns an instance of InorderIterator (line 215).

The InorderIterator constructor invokes the inorder method (line 225). The inorder(root) method (lines 234–239) stores all the elements from the tree in list. The elements are traversed in inorder.

Once an Iterator object is created, its current value is initialized to 0 (line 222), which points to the first element in the list. Invoking the next() method returns the current element and moves current to point to the next element in the list (line 250).

The hasNext() method checks whether current is still in the range of list (line 243).

The remove() method removes the current element from the tree (line 256). Afterward, a new list is created (lines 257–258). Note that current does not need to be changed.

The code below gives a test program that stores the strings in a BST and displays all strings in uppercase.

The foreach loop (lines 15–16) uses an iterator to traverse all elements in the tree.

Iterator is an important software design pattern. It provides a uniform way of traversing the elements in a container, while hiding the container’s structural details. By implementing the same interface java.util.Iterator, you can write a program that traverses the elements of all containers in the same way.

java.util.Iterator defines a forward iterator, which traverses the elements in the iterator in a forward direction, and each element can be traversed only once. The Java API also provides the java.util.ListIterator, which supports traversing in both forward and backward directions. If your data structure warrants flexible traversing,
you may define iterator classes as a subtype of java.util.ListIterator.

The implementation of the iterator is not efficient. Every time you remove an element through the iterator, the whole list is rebuilt (line 257 in BST.java). The client should always use the delete method in the BinraryTree class to remove an element. To prevent the user from using the remove method in the iterator, implement the iterator as follows:

public void remove() {
throw new UnsupportedOperationException
("Removing an element from the iterator is not supported");
}

After making the remove method unsupported by the iterator class, you can implement the iterator more efficiently without having to maintain a list for the elements in the tree. You can use a stack to store the nodes, and the node on the top of the stack contains the element that is to be returned from the next() method. If the tree is well-balanced, the maximum stack size will be O(logn).