public class BSTIterator {
Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode>();
addLeftNodes(root);
}
void addLeftNodes(TreeNode node) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode next = stack.pop();
// Add its right node's left nodes onto stack
addLeftNodes(next.right);
return next.val;
}
}
Can anyone verify if this is O(1) time O(h) space solution?


Yes. Your next() runs in average O(1) time.
The *next()*it is called n times, while in all the runtime of next(), each of the n nodes enters the stack at most 1 time (some nodes enter during construction) and leaves the stack exactly 1 time.And the space cost is O(h) time.
The stack size grows only in addLeftNodes().
Each time addLeftNodes() finishes, the node at top of the stack is a leaf.
At the same time, right below each node is its parent or the parent of its parent.
Thus, after addLeftNodes(), the node sequence in stack forms a (sometimes incompleted) path from root to a leaf. Such a path always has a length less than the height of the tree.