title: Java - Binary Search Tree has a iterator() method, difficulty with implementing
body: <p>I'm trying to write an implementation of iterator so that I can call it 
  within my BST class, under iterator() method.</p>
  
  <p>My solution (not sure if it would work correctly) is to use a stack or a queue to 
  store the nodes of the BST. Trouble is, my Iterator Implementation class can't recognise my 
  BST nodes when I pass the "root" node into its constructor.</p>
  
  <p>For your ease of imagination, this is my BST implementation, it works fine for other methods including add, delete, etc. But I'm currently stuck at the <code>iterator()</code> method. Since I have no idea how to start and what to do.</p>
  
  <pre><code>   public class DictionaryImp&lt;E extends Comparable&lt;E&gt;&gt; implements Dictionary&lt;E&gt; {
  
          public class DictNode {
             public DictNode left;
             public DictNode right;
             public String position;
             public E value;
  
             public DictNode(E value, DictNode left, DictNode right, String position) {
                 this.left = left;
                 this.right = right;
                 this.position = position;
                 this.value = value;
             }
          }
  
         public DictNode root;
  
         //... more code
  
         public Iterator&lt;E&gt; iterator() {
               // provides a fail fast iterator for the Dictionary
               // starting at the least element greater than or equal to start
               Iterable&lt;E&gt; itr = new DictionaryItr&lt;E&gt;(root);
               Iterator&lt;E&gt; it = itr.iterator();
               return it;
         }
  }
  </code></pre>
  
  <p>This is what I wrote for the Iterator implementation</p>
  
  <pre><code>public class DictionaryItr&lt;E&gt; implements Iterable&lt;E&gt; {
      public DictionaryItr(DictNode root) {
          first = null;
          this.inOrderTraversial(root);
      }
  
      public void inOrderTraversial(DictNode node) {
          if (node != null) {
              inOrderTraversial(node.left);
              first.push(node.value);
              inOrderTraversial(node.right);
          }
      }
  
      // more code: push, peek, pop
  
      public Iterator&lt;E&gt; iterator() {
          return new ListIterator();
      }
      private class ListIterator implements Iterator&lt;E&gt; {
          private Node current = first;
          public boolean hasNext()  { return current != null;                     }
          public void remove()      { throw new UnsupportedOperationException();  }
  
          public E next() {
              if (!hasNext()) throw new NoSuchElementException();
              E item = current.item;
              current = current.next; 
              return item;
          }
      }
  }
  </code></pre>