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

The root is the first node to be visited in preorder. After we visit this node we must traverse the left subtree and then return to traverse the right subtree. To enable the return to the right subtree, we save a pointer to the root of this right subtree on a stack provided the right subtree is not empty. When we are traversing the left subtree of the root, its root is visited a pointer to its nonempty right subtree is saved on the stack, and we proceed to traverse its left subtree. When we are done with the traversal of the left subtree, we move into its right subtree (if it is nonempty) or into the right subtree of the nearest ancestor that has a nonempty right subtree. This is done by removing the right subtree root pointer from the top of the stack.

The code is given below. A test program and corresponding output are given in the files IterativePreorderTraversal.*. 
public class IterativePreorderTraversal
{
   /** visit method that prints the element in the node */ 
   public static void visit(BinaryTreeNode t)
      {System.out.print(t.element + " ");}

   /** preorder traversal */
   public static void preOrder(BinaryTreeNode t)
   {
      ArrayStack stack = new ArrayStack(10);
      BinaryTreeNode currentNode = t;
      while (true)
      {// traverse subtree rooted at currentNode in preorder

         // is subtree empty
         if (currentNode == null)
            // yes it is, get a subtree to traverse from the stack
            try
            {
               currentNode = (BinaryTreeNode) stack.pop();
            }
            catch (Exception e)
            {// no untraversed subtrees left
               return;
            }
   
         // first visit the root of the subtree
         visit(currentNode);
   
         // save pointer to right subtree for future traversal
         if (currentNode.rightChild != null)
            stack.push(currentNode.rightChild);
   
         // move into left subtree
         currentNode = currentNode.leftChild;
      }
   }
}


The stack never contains two pairs that correspond to nodes on the same level. When we reach a leaf the stack contains pointers to nonempty right subtrees of nodes on the path from the root to that leaf. So the stack space needed as well as the overall space needed by the traversal is O(h) where h is the height of the binary tree that is being traversed. Notice that when a left-skewed binary tree is traversed nothing is added to the stack.