On this page

Binary Search Tree Iterator

Implement a BSTIterator class that iterates over a BST in inorder (ascending order):

  • BSTIterator(TreeNode root) initializes the iterator.
  • int next() returns the next smallest number.
  • boolean hasNext() returns true if there is a next number.

The ideal solution uses O(h) memory and next() / hasNext() run in average O(1) time.

Constraints:

  • The number of nodes is in the range [1, 10^5].
  • 0 <= Node.val <= 10^6, and at most 10^5 calls are made.

Intuition

1 8
2 / \
3 4 12
4 / \ / \
5 2 6 10 14

The easy solution is to do a full inorder traversal in the constructor, store the values in an array, and walk through it. It works, but uses O(n) memory, and we are asked to use only O(h).

Instead, pause the iterative inorder traversal between calls. The stack in the iterative inorder already represents "the path to the next node". If we keep that stack as the iterator's state, each call to next() just advances it by one step.

Approach: A Stack That Holds the Left Spine

  • Constructor: push the root and every node down its left spine. The top of the stack is now the smallest value.
  • next(): pop the top node. That is the answer. Then push the left spine of its right child (if any), so the stack top is the next smallest node. Return the popped value.
  • hasNext(): return whether the stack is non-empty.

Each node is pushed and popped exactly once over the whole iteration, so next() is O(1) amortized. The stack never holds more than one root-to-node path, so memory is O(h).

Code

class BSTIterator {
stack<TreeNode*> st;
void pushLeft(TreeNode* node) {
while (node != nullptr) {
st.push(node);
node = node->left;
}
}
public:
BSTIterator(TreeNode* root) {
pushLeft(root);
}
int next() {
TreeNode* node = st.top();
st.pop();
pushLeft(node->right);
return node->val;
}
bool hasNext() {
return !st.empty();
}
};

Complexity

Time: O(1) amortized per call

Each node is pushed once and popped once across the whole iteration, so n calls to next() cost O(n) in total. A single call can take O(h) in the worst case.

Space: O(h)

The stack holds at most one root-to-node path, instead of all n values.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"The simple solution stores a full inorder traversal in an array, but that is O of n memory, and the goal is O of h. So I keep the state of an iterative inorder traversal in a stack. In the constructor I push the root and its whole left spine, so the top is the smallest value. For next, I pop the top node, then push the left spine of its right child so the stack is ready for the next call, and return the popped value. hasNext just checks that the stack is not empty. Each node is pushed and popped once overall, so next is O of one amortized, and the stack holds one path, so memory is O of h."
Next TopicTwo Sum IV Input Is a Bst