DSA · Trees · #42
Binary Search Tree Iterator
Module 44 · difficulty 3/5·⏱ 30:00starts on first keystroke
Implement the class `BSTIterator` that represents an in-order iterator over a binary search tree (BST): - `new BSTIterator(root)` initializes an object. The pointer is positioned at a non-existent number smaller than any element in the BST. - `hasNext()` returns `true` if there exists a number in the traversal to the right of the pointer, otherwise `false`. - `next()` moves the pointer to the right, then returns the number at the pointer. Calls to `next()` return BST values in **ascending** order. Each tree node is `{ val, left, right }` with `left`/`right` defaulting to `null`. It is guaranteed that `next()` is only called when `hasNext()` is `true`. Aim for average `O(1)` time per call and `O(h)` memory, where `h` is the tree height.
Examples
ops = ["BSTIterator","next","next","hasNext","next","hasNext","next","hasNext","next","hasNext"] args = [[[7,3,15,null,null,9,20]],[],[],[],[],[],[],[],[],[]]→[null,3,7,true,9,true,15,true,20,false]— In-order traversal of the tree yields 3,7,9,15,20.ops = ["BSTIterator","hasNext","next"] args = [[[1]],[],[]]→[null,true,1]— Single-node tree.
Constraints
- · The number of nodes in the tree is in the range [1, 10^5].
- · 0 <= Node.val <= 10^6
- · At most 10^5 calls will be made to hasNext and next.
- · next() is only called when hasNext() returns true.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.