public class BSTIterator {
private Queue<Integer> queue = new LinkedList<Integer>();
public BSTIterator(TreeNode root) {
dfsTree(root);
}
private void dfsTree(TreeNode node) {
if( node != null) {
dfsTree(node.left);
queue.add(node.val);
dfsTree(node.right);
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !queue.isEmpty();
}
/** @return the next smallest number */
public int next() {
if( hasNext() ) {
return queue.remove();
}
else {
return 0;
}
}
}
Simple and efficient Java solution by DFS + Queue



@manu5 Yes, I believe it's space complexity is O(n) as I put all values of nodes into the queue.