Reviewing the PreorderIterator class

Overview

In Problem Set 8, you will implement a postorder iterator for a binary tree. In this document, we review the preorder iterator that we’ve given you as a model.

Much like the linked-list iterator that we considered earlier in the course, a binary-tree iterator allows a client to gradually iterate over the items in a collection. In a singly linked list, there is only one way to traverse the list, and thus there was only one type of iterator. In a binary tree, on the other hand, there are multiple ways to traverse the tree, and thus there are multiple possible iterators.

Regardless of the type of iterator, we want it to implement the following interface:

public interface LinkedTreeIterator {
    // are there other nodes to see in this traversal?
    boolean hasNext();

    // return the value of the key in the next node in the traversal, 
    // and advance the position of the iterator
    int next();
}

Note that the next() method returns an int, because we have restricted our LinkedTree class to have keys that are integers.

If we create a preorder iterator object and repeatedly invoke its next() method, we should visit the nodes of the tree in the order taken by a preorder traversal. If we create a postorder iterator object and repeatedly invoke its next() method, we should visit the nodes of the tree in the order taken by an postorder traversal.

Class header and fields

Each type of iterator will be implemented as a private inner class of the LinkedTree class. For the PreorderIterator class that we have provided as a model, the beginning of the class looks like this:

public class LinkedTree {
    ...
    private class PreorderIterator implements LinkedTreeIterator {
        private Node nextNode;

Notice that:

• The class is a private inner class, because it is defined within the LinkedTree class and it is declared to be private. Making it an inner class gives the iterator object access to the private fields of the associated LinkedTree object.

• We include a clause in the class header that specifies that the class implements the LinkedTreeIterator interface that we discussed earlier.

• The class has only one field. It is called nextNode, and it will hold a reference to the next Node object to be visited by the iterator.

Constructor

The constructor for an iterator needs to initialize the nextNode field so that it refers to the first node to be visited by the iterator.

The constructor of the PreorderIterator class looks like this:

public PreorderIterator() {
    nextNode = root;
}

In the case of a preorder iterator, the first node to be visited is the root of the tree as a whole, which is why the above constructor is so simple. It can simply copy the reference stored in the root field of the associated LinkedTree object into the nextNode field of the new PreorderIterator object. (Because PreorderIterator is an inner class, it has access to the fields of the LinkedTree object that is used to create it.)

However, for a postorder iterator, the first node visited is not necessarily the root of the tree as a whole, and thus you will need to perform whatever steps are needed to find the first node that the postorder iterator should visit, and to initialize the iterator’s field accordingly. Considering several concrete cases should help you to figure out the logic.

hasNext() method

The hasNext() method of the PreorderIterator class looks like this:

public boolean hasNext() {
    return (nextNode != null);
}

This method is also quite simple. There are other nodes to visit as long as nextNode is not null; when this is the case, this method will return true. When the traversal is completed, nextNode will become null, and this method will return false.

next() method

The next() method must do two things:

• It must return the value of the key in the next node to be visited.

• It must advance the iterator so that it is ready for the next call to this method.

The PreorderIterator version of this method begins as follows:

public int next() {
    if (nextNode == null) {
        throw new NoSuchElementException();
    }
    ...

}

This initial if statement handles cases in which the method is called when there are no remaining nodes to visit.

Next, the method uses a local variable to store a copy of the key in the Node to which nextNode currently refers:

public int next() {
    ...
    int key = nextNode.key;
    ...
}

This must be done before the iterator is advanced, because we will lose access to this key after nextNode is advanced.

After storing the key, the next() method must advance nextNode to make it refer to the next node to be visited.

By considering concrete examples, we can see that there are several different cases that the method needs to handle. These cases depend on the number and types of children of the node whose key we are about to return (which we will refer to as the current node in the discussion below).

Case 1: The current node has a left child. For example, this case would hold if nextNode were currently pointing to the 44, 35, 53, or 62 nodes in the following tree:

A preorder traversal visits the root, then it recursively traverses the left subtree, then it recursively traverses the right subtree. Therefore, if the current node has a left child, the next node to be visited is the left child, since it is the root of the left subtree. The next() method handles this case as follows:

public int next() {
    ...
    if (nextNode.left != null) {
        nextNode = nextNode.left;
    }
    ...
}

Case 2: The current node does not have a left child, but it does have a right child. For example, this case would hold if nextNode were currently pointing to the 23 node in the tree above.

In this case, because there is no left subtree, the traversal goes next to the right subtree, and thus the next node to be visited is the current node’s right child, since it is the root of the right subtree.

The next() method handles this case using an else-if:

public int next() {
    ...
    if (nextNode.left != null) {
        nextNode = nextNode.left;
    } else if (nextNode.right != null) {
        nextNode = nextNode.right;
    }
    ...
}

Note that we won’t even make it to the else-if unless the original if condition is false, and thus we will only execute the else-if block if nextNode does not have a left child (i.e., if nextNode.left is null) but it does have a right child (i.e., nextNode.left is not null).

Case 3: The current node is a leaf node (e.g., if the current node is 28, 48, 57, or 80 in the tree above). In this case, we need to go back up the tree, looking for nodes that have yet to be visited.

Because a preorder traversal visits a node as soon as it encounters it (since the root of any tree/subtree is visited first) and because it then visits the left subtree, the only unvisited nodes are in right subtrees of nodes that we’ve already visited. Thus, the method needs to trace back up using parent references (see the important note above) until we find a node with a right child on a different path from the one that we took to get to the current node.

The next() method handles this third case in the else block. It begins with a while loop that traces back up the tree, looking for a node with an unvisited right child:

public int next() {
    ...
    if (nextNode.left != null) {
        nextNode = nextNode.left;
    } else if (nextNode.right != null) {
        nextNode = nextNode.right;
    } else {
        Node parent = nextNode.parent;
        Node child = nextNode;
        while (parent != null && 
               (parent.right == child || parent.right == null)) {
            child = parent;
            parent = parent.parent;
        }

        ...
    }
    ...
}

Note that this loop uses two references as it traces up: one called parent, which is like the trav reference that we use in linked-list traversals; and one called child, which is a trailing reference that stays one behind parent.

The reason that we need a trailing reference is that the loop needs to distinguish between right children that are on the path from the root to the current node (which have already been visited) and right children that are not on that path (and have yet to be visited).

For example, consider again the following tree:

After visiting the 28 node, we need to go all the way back up to the 44 node so that we can then make nextNode refer to its right child (the 53). That’s because 44 is first node that we encounter on the way back up that has an unvisited right child.

If we aren’t careful, we might mistakenly use the following loop that doesn’t use a trailing reference:

Node parent = nextNode.parent;
while (parent != null && parent.right == null) {
    parent = parent.parent;
}

However, this loop will stop whenever it finds a node with a right child (i.e., whenever parent.right is not null). If the current node is the 28 node, this loop would actually stop at the 23 node, because 23 is a node with a right child. However, we don’t want to stop there, because 28 has already been visited! We want to go all the way up to the 44.

This is why we need to use the trailing child reference and to expand the second while loop condition to be

(parent.right == child || parent.right == null)

The added condition parent.right == child means that we won’t always stop looping when we encounter a node with a right child. Rather:

• If the right child is on the path that we’re going up (for example, if parent is pointing to the 23 node and child is pointing to the 28 node), the added condition will be true (because 23’s right child is the 28), and we will keep looping.

• If the right child is not on the path that we’re going up (for example, if parent is pointing to the 44 node and child is pointing to the 35 node), the added condition will be false (because 44’s right child is not the 35 node), and we will stop looping.

Once we stop looping, there are two possibilities:

• The final value of the parent reference is null. This means that there is nothing left to visit.

• Otherwise, the next node that should be visited is the right child of the node to which parent refers (e.g., the 53, when parent ends up pointing to 44).

The if-else statement after the while loop handles both of these cases:

if (parent == null) {
    nextNode = null;   // the traversal is complete
} else {
    nextNode = parent.right;
}

Finally, the next() method returns the key that was stored earlier.

Here is the complete next() method:

public int next() {
    if (nextNode == null) {
        throw new NoSuchElementException();
    }

    // Store a copy of the key to be returned.
    int key = nextNode.key;

    // Advance nextNode.
    if (nextNode.left != null) {
        nextNode = nextNode.left;
    } else if (nextNode.right != null) {
        nextNode = nextNode.right;
    } else {
        // We've just visited a leaf node.
        // Go back up the tree until we find a node
        // with a right child that we haven't seen yet.
        Node parent = nextNode.parent;
        Node child = nextNode;
        while (parent != null &&
               (parent.right == child || parent.right == null)) {
            child = parent;
            parent = parent.parent;
        }

        if (parent == null) {
            nextNode = null;  // the traversal is complete
        } else {
            nextNode = parent.right;
        }
    }

    return key;
}