#173
Binary Search Tree Iterator
Medium Controlled inorder with a stack
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Build an iterator over a BST that returns values in increasing order with next() and hasNext(), using O(h) memory.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: return values in sorted order one at a time using O(h) memory.
Why this works: keep only the left spine on a stack (a paused inorder traversal); after popping a node, push the left spine of its right child.
Example: 7 (3, 15 (9, 20))
stack [7, 3] → next 3next 7 → push 15, 9 → next 9, 15, 20
✦Hints open one at a time
Store only the path of left children, like an iterative inorder paused between steps.
next(): pop a node, then push the left spine of its right child.
↗Approach
Constructor pushes the left spine of the root. next pops the top, pushes the left spine of its right subtree, and returns the value. hasNext checks the stack.
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class BSTIterator {
private final Deque<TreeNode> st = new ArrayDeque<>();
public BSTIterator(TreeNode root) {
pushLeft(root);
}
public int next() {
TreeNode n = st.pop();
pushLeft(n.right); // next smallest values are in the right subtree
return n.val;
}
public boolean hasNext() {
return !st.isEmpty();
}
private void pushLeft(TreeNode n) {
while (n != null) {
st.push(n);
n = n.left;
}
}
}!Common mistake
Flattening the whole tree into a list in the constructor — O(n) memory.
Complexity
- Time: Amortised O(1) per next().
- Space: O(h).
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon