Data Structures, Algorithms, & Applications in Java
Chapter 12, Exercise 47

We shall esentially perform a preorder traversal of the binary tree. The preorder traversal will need to be suspended whenever we find a node to visit because this node contains the element to be returned by next(). To find the next element in preorder, we will need to resume the traversal beginning at the current node. This resumption is best done by implementing the preorder traversal nonrecursively.

The constructor method for the enumerator must position us at the first node visited by a preorder traversal. This node is the root of the tree.

The method next() needs to simulate the portion of a preorder traversal from the visit of the last node to the visit of the next node. If the last node that was visited has a non null right subtree, this subtree should be saved on a stack so that it can be processed after we process the left subtree of the last node that was visited. Following this saving of the right subtree on a stack, we can determine the next node in preorder. This next node is the root of the left subtree of the last node that was visited, unless this left subtree is empty. When this left subtree is empty, the next node to visit is the node at the top of the stack. When the stack is empty, there is no next node.

The code is given below.
public class LinkedBinaryTreeWithPreorderIterator extends LinkedBinaryTree
{
   /** create and return an enumerator */
   public Iterator iterator()
      {return new PreorderIterator();}

   /** preorder enumerator */
   private class PreorderIterator implements Iterator
   {
      // data members
      private BinaryTreeNode nextNode;  // next node in preorder
      private ArrayStack stack = new ArrayStack(10);
   
      // constructor
      /** set nextNode to first node in preorder */
      public PreorderIterator()
         {nextNode = root;}
   
      // methods
      /** @return true iff tree has more elements */
      public boolean hasNext()
      {
         return nextNode != null;
      }

      /** @return next element in preorder
        * @throws NoSuchElementException
        * when there is no next element */
      public Object next()
      {
         if (nextNode != null)
         {
            // save next preorder element
            Object obj = nextNode.element;
            
            // put right subtree on the stack if not null
            if (nextNode.rightChild != null)
               // right subtree will be examined later
               stack.push(nextNode.rightChild);

            // set nextNode to next node in preorder
            if (nextNode.leftChild != null)
               // root of left subtree is the next node in preorder
               nextNode = nextNode.leftChild;
            else
            {// get next preorder node from the stack
               try
               {
                  nextNode = (BinaryTreeNode) stack.pop();
               }
               catch (Exception e)
               {// no node to back up to
                  nextNode = null;
               }
            }
            return obj;
         }
         else throw new NoSuchElementException("No next element");
      }

      /** unsupported method */
      public void remove()
      {
         throw new UnsupportedOperationException
                   ("remove not supported");
      }   
   }
}



The complexity of each iterator method (exclusive of the time needed to double the stack size when needed) is readily seen to be O(1). If a linked stack is used in place of an array stack, then the complexity of each method (including all steps) is O(1). The stack space is O(h).