MediumNeetCode150StackTreeDesignBinary Search TreeBinary Tree
Binary Search Tree Iterator
Implement BST iterator.
Examples
Input
BSTIterator operations: next, next, hasNext, next, hasNext, next, hasNext
Output
3,7,true,9,true,15,true
Inorder: 3,7,9,15,20.
Constraints
- •
Number of nodes in [1,10^5] - •
0 <= Node.val <= 10^6 - •
At most 10^5 calls
Approaches
Inorder traverse, store.
CodeT: O(n) init | S: O(n) storage
Push nodes along left path.
CodeT: O(h) init | S: O(h) stack
Same approach.
CodeT: O(1) amortized next | S: O(h)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Store All | O(n) init | O(n) storage | Inorder traverse, store. |
| Stack | O(h) init | O(h) stack | Push nodes along left path. |
| Stack Optimized | O(1) amortized next | O(h) | Same approach. |
Store All
T: O(n) initS: O(n) storage
Inorder traverse, store.
Stack
T: O(h) initS: O(h) stack
Push nodes along left path.
Stack Optimized
T: O(1) amortized nextS: O(h)
Same approach.
Common Mistakes
Not using stack
Not pushing all left nodes
Off-by-one in next