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

We shall esentially perform a level order traversal of the binary tree. The level order 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 level order, we will need to resume the traversal beginning at the current node.

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

The method next() needs to simulate the portion of a level order traversal from the visit of the last node to the visit of the next node. For this, we simply add the up to two children of the last node visited to a queue and then extract the first node from the queue. This extracted node is the next level order node. By using a linked queue rather than an array queue, we ensure that the complexity of each method is O(1).

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

   /** level order iterator */
   private class LevelorderIterator implements Iterator
   {
      // data members
      private BinaryTreeNode nextNode;  // next node in level order
      private ArrayQueue queue = new ArrayQueue();
   
      // constructor
      /** set nextNode to first node in level order */
      public LevelorderIterator()
         {nextNode = root;}
   
      // methods
      /** @return true iff tree has more iterator */
      public boolean hasNext()
         {return nextNode != null;}

      /** @return next element in level order
        * @throws NoSuchElementException
        * when there is no next element */
      public Object next()
      {
         if (nextNode != null)
         {
            // save next level order element
            Object obj = nextNode.element;

            // put children on queue
            if (nextNode.leftChild != null) 
               queue.put(nextNode.leftChild);
            if (nextNode.rightChild != null)
               queue.put(nextNode.rightChild);
      
            // get next node to visit
            nextNode = (BinaryTreeNode) queue.remove();
            
            return obj;
         }
         else throw new NoSuchElementException("No next elemnt");
      }

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