```
public class BSTIterator {
private TreeNode head = null;
private Stack<Integer> stack = new Stack<>();
public BSTIterator(TreeNode root) {
head = root;
DFS(head,stack);//in-order DFS;
}
private void DFS(TreeNode root, Stack<Integer> stack){
if(root==null) return;
//notice we need the top of the stack to have the smallest num so far;
DFS(root.right, stack);
stack.push(root.val);
DFS(root.left, stack);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
if(!stack.isEmpty()) return true;
else return false;
}
/** @return the next smallest number */
public int next() {
return stack.pop();
}
}
```