/*BS ITERATOR
  Giri Gopalan
  2/17/05 */
import java.util.*;
public class traverse implements Iterator
 {
  private Stack s = new Stack(); //temp holder of nodes
  private node cur;              //position holder in tree
  private boolean flag;          //flag for getNext method

  public traverse (node root)  //initializes current node and sets boolean flag  
   {                           // to false
    cur = root;
    flag = false;
   }
  public boolean hasNext() //if cur is not null --> more stuff to process --> 
   {                                                               //return true
    if (cur != null)
     return true;
    else
     return false;
   }
  public Object next()
   {
    Object print = null; 
    while (print == null)
     {
      if (cur.left != null && flag == false) //travel left to a leaf, push 
       { s.push(cur); cur = cur.left; }      //intermediate nodes onto stack
      else
       {
        print = cur.data;        //data of next node to be processed store in 
        if (cur.right != null)   //print go to right subtree if it exists
         {flag = false; cur = cur.right;}
        else if(s.isEmpty() == false) //otherwise pop a node off the stack if 
         {flag = true; cur = (node)s.pop();}         //its not empty
        else
         cur = null;              //otherwise, all nodes are processed
       }
    }
    return print;
   }
 public void remove()
  {}
 }