0)  a, b, d, e, h, j, c, f, i, g

1)  We only need a single field: a reference called nextNode to the
    next node to be visited.

2)  The constructor needs to make nextNode refer to the first node to
    be visited by the iterator. Since a preorder traversal begins
    by visiting the root of the tree, the constructor is very simple:

        private PreorderIterator() {
            nextNode = root;
        }

    Note that root is a field of the LinkedTree class.
    Because PreorderIterator is an inner class, it has access to the
    field of the tree object that was used to create it.

    In PS 8, your constructor will *not* be this simple, because
    you'll need to navigate to the first node to be visited.

3)  hasNext() is also quite simple. There are more nodes to visit as long
    as nextNode is not null:

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

4)  We can throw a NoSuchElementException.

5)  We need to updated the nextNode field.

6)  We must first save a copy of the current node's key, so that we
    can return it at the end of the method.

7)  *Case 1*. The current node has a left child (e.g., if the current
    node is a, b, or e in the example). 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, then the next node to be visited is the
    left child, since it is the root of the left subtree.

    *Case 2*. The current node does not have a left child, but it does have
    a right child (e.g., if the current node is f). 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.

    *Case 3*. The current node is a leaf node (e.g., if the current
    node is d, j, i or g). 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 (i.e., the root is visited first) and then visits
    the left subtree, the only unvisited nodes are in right subtrees
    of nodes that we've already visited. Thus, we can trace back up
    using parent references 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 following code *almost* works:

        // warning: doesn't work in all cases!
        Node p = nextNode.parent;
        
        while (p != null && p.right == null) {
            p = p.parent;
        }

        if (p == null) {
            nextNode = null;
        } else { 
            nextNode = p.right;
        }

    However, this code fails 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, if the current
    node is the j node, the above code would cause the iterator to
    revisit the e node the next time the `next()` method is called,
    since e is the right child of its parent.  Instead, we want the
    iterator to visit the c node next. We can get around this problem
    by using two different references as we trace back up the tree:
    one to perform the traversal, and one to stay one node "behind"
    the first reference. That will allow us to find previously
    unvisited right children.

        Node p = nextNode.parent;
        Node c = nextNode; 
        
        while (p != null && (p.right == null || p.right == c)) {
            c = p;
            p = p.parent;
        }
        
        if (p == null) {
            nextNode = null;
        } else { 
            nextNode = p.right;
        }

8)  We return the key we saved before we updated nextNode.

Here is the full next() method:

    public int next() {
        // code to handle nextNode == null goes here

        int key = nextNode.key;
        
        if (nextNode.left != null) {
            nextNode = nextNode.left;
        } else if (nextNode.right != null) {
            nextNode = nextNode.right;
        } else {
            // warning: doesn't work in all cases!
            Node p = nextNode.parent;

            while (p != null && p.right == null) {
                p = p.parent;
            }
        
            if (p == null) {
                nextNode = null;
            } else { 
                nextNode = p.right;
            }
        }
        
        return key;
    }