173. Binary Search Tree Iterator

 1 public class BSTIterator {
 2     Stack<TreeNode> stack;
 3     
 4     public BSTIterator(TreeNode root) {
 5         stack = new Stack<TreeNode>();
 6         TreeNode cur = root;
 7         while(cur != null) {
 8             stack.push(cur);
 9             cur = cur.left;
10         }
11     }
12 
13     /** @return whether we have a next smallest number */
14     public boolean hasNext() {
15         return !stack.isEmpty();
16     }
17 
18     /** @return the next smallest number */
19     public int next() {
20         TreeNode cur = stack.pop();
21         int next = cur.val;
22         cur = cur.right;
23         while(cur != null) {
24             stack.push(cur);
25             cur = cur.left;
26         }
27         return next;
28     }
29 }