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