```
Queue<TreeNode> queue;
public BSTIterator(TreeNode root) {
queue = new LinkedList<TreeNode>();
pre(root);
}
public void pre(TreeNode root){
if(root == null) return;
pre(root.left);
queue.add(root);
pre(root.right);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !queue.isEmpty();
}
/** @return the next smallest number */
public int next() {
return queue.poll().val;
}
```