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

We shall esentially perform a postorder traversal of the binary tree. The postorder 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 postorder, we will need to resume the traversal beginning at the current node. This resumption is best done by implementing the postorder traversal nonrecursively.

Exercise 12.32 does an iterative postorder traversal. You are urged to read the solution to Exercise 12.32 before proceeding. The constructor method for the enumerator must position us at the first node visited by a postorder traversal. This node is the leftmost leaf of the tree and is found by starting at the root and traversing a leaftmost path until a leaf is reached. Each node we make a move from is saved on a stack. As in Exercise 12.32, we need to distinguish between left child and right child moves made during this search for the left most leaf. So, we use the class StackElement defined in Exercise 12.32. Also, the code used to search for the leftmost leaf in the tree is written as a method which can actually find the leftmost leaf in any subtree.

Once we have identified the left most leaf, this node is saved in the data member nextNode. This data member gives us the next postorder node and it is null iff there is no next postorder node in the tree.

The code for the constructor and the methods iterator, leftMostLeaf, and hasNext is given below. 
public class LinkedBinaryTreeWithPostorderIterator extends LinkedBinaryTree
{
   // define a class for use by the iterator
   static class StackElement
   {
      // data members
      BinaryTreeNode node;
      boolean leftChild;   // true iff we move to the left child of node

      // constructor
      public StackElement(BinaryTreeNode theNode, boolean theLeftChild)
      {
         node = theNode;
         leftChild = theLeftChild;
      }
   }

   /** create and return an iterator */
   public Iterator iterator()
      {return new PostorderIterator();}

   /** postorder iterator */
   private class PostorderIterator implements Iterator
   {
      // data members
      private BinaryTreeNode nextNode;  // next node in postorder
      private ArrayStack stack = new ArrayStack(10);
   
      // constructor
      /** set nextNode to first node in postorder */
      public PostorderIterator()
         {nextNode = (root == null) ? null : leftMostLeaf(root);}
   
      // methods
      /** @return the leftmost leaf in the subtree with root t
        * save nodes on the path to this leaf on the stack */
      BinaryTreeNode leftMostLeaf(BinaryTreeNode t)
      {
         BinaryTreeNode currentNode = t;
         while (true)
         {
            // move to leftmost node in subtree
            while (currentNode.leftChild != null)
            {
               stack.push(new StackElement(currentNode, true));
               currentNode = currentNode.leftChild;
            }

            // is this node a leaf?
            if (currentNode.rightChild == null)
               // it is a leaf, must be leftmost leaf
               return currentNode;

            // leftmost leaf is in right subtree of currentNode
            stack.push(new StackElement(currentNode, false));
            currentNode = currentNode.rightChild;
         }
      }

      /** @return true iff tree has more iterator */
      public boolean hasNext()
         {return nextNode != null;}

      /** return next element in postorder
        * throws NoSuchElementException
        * when there is no next element */
      public Object next()
      {
         if (nextNode != null)
         {
            Object obj = nextNode.element;
            
            // determine next postorder node
            if (stack.empty())
            {// there is no next node
               nextNode = null;
            }
            else
            {// there is a next node
               StackElement sElement = (StackElement) stack.pop();
               nextNode = sElement.node;
               if (sElement.leftChild && nextNode.rightChild != null)
               {// returning from left subtree of nextNode
                // incorrect nextNode, correct next node is leftmost
                // leaf in right subtree of nextNode
                  stack.push(new StackElement(nextNode, false));
                  nextNode = leftMostLeaf(nextNode.rightChild);
               }
            }
            return obj;
         }
         else throw new NoSuchElementException("No next element");
      }

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


The method next() needs to simulate the portion of a postorder traversal from the visit of the last node to the visit of the next node. This is done by backing up from the last node visited to the node topNode at the top of the stack. If we are backing up from the right subtree of topNode or if topNode has an empty right subtree, topNode is the next postorder node. If we are backing up from the left subtree of topNode and if topNode has a nonempty right subtree, then the next postorder node is the leftmost leaf in this nonempty right subtree. The code is given below. 
/** @return next element in postorder
  * @throws NoSuchElementException
  * when there is no next element */
public Object next()
{
   if (nextNode != null)
   {
      Object obj = nextNode.element;
      
      // determine next postorder node
      if (stack.empty())
      {// there is no next node
         nextNode = null;
      }
      else
      {// there is a next node
         StackElement sElement = (StackElement) stack.pop();
         nextNode = sElement.node;
         if (sElement.leftChild && nextNode.rightChild != null)
         {// returning from left subtree of nextNode
          // incorrect nextNode, correct next node is leftmost
          // leaf in right subtree of nextNode
            stack.push(new StackElement(nextNode, false));
            nextNode = leftMostLeaf(nextNode.rightChild);
         }
      }
      return obj;
   }
   else throw new NoSuchElementException("No next element");
}


Since our codes break up a postorder traversal into several steps, the time needed to get all elements in a tree using an enumerator is the same as that needed to perform a postorder traversal, that is O(n), where n is the number of nodes in the tree. So the average time per invocation is O(1). The stack height and the complexity of each method are readily seen to be O(h).