173. Binary Search Tree Iterator

It is the same algorithm as we do the inorder traversal. Use O(h) memory with stack. The hasNext has worst O(1) run time while next() has worst O(h) time and average O(1) run time.

 public class BSTIterator {  
   Stack<TreeNode> st;  
   TreeNode cur;  
   public BSTIterator(TreeNode root) {  
     st=new Stack<TreeNode>();  
     cur=root;  
     while(cur!=null){  
       st.push(cur);  
       cur=cur.left;  
     }  
   }  
   /** @return whether we have a next smallest number */  
   public boolean hasNext() {  
     return cur!=null || !st.empty();  
   }  
   /** @return the next smallest number */  
   public int next() {  
     while(cur!=null){  
       st.push(cur);  
       cur=cur.left;  
     }  
       TreeNode temp=st.pop();  
       int res=temp.val;  
       cur=temp.right;  
     return res;  
   }  
 }