Leetcode 173 Binary Search Tree Iterator

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 1: Use iterative in-order traversal.

 public class BSTIterator {  
   private TreeNode x;  
   private Deque<TreeNode> stack;  
   public BSTIterator(TreeNode root) {  
     stack=new LinkedList<>();  
     x=root;  
     while (x!=null) {  
       stack.push(x);  
       x=x.left;  
     }  
   }  
   /** @return whether we have a next smallest number */  
   public boolean hasNext() {  
     return !stack.isEmpty();  
   }  
   /** @return the next smallest number */  
   public int next() {  
     x=stack.pop();  
     int res=x.val;  
     x=x.right;  
     while (x!=null) {  
       stack.push(x);  
       x=x.left;  
     }  
     return res;  
   }  
 }}