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()returnstrueif 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 most10^5calls are made.
Intuition
1 82 / \3 4 124 / \ / \5 2 6 10 14The 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
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.
The stack holds at most one root-to-node path, instead of all n values.