173. Binary Search Tree Iterator Leetcode Java

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Solution:

It is essentially an in order traversal. See 94. Binary tree in order traversal

Here I use a stack to realize the in order traversal. 

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