# Can anyone verify if this is O(1) time O(h) space solution?

• ``````public class BSTIterator {
Stack<TreeNode> stack;

public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode>();
}

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
return next.val;
}
}``````

• 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.