Binary Search Tree Iterator
Medium · Trees · Stack · Tree · Design · Binary Search Tree · Iterator
Problem
Implement a class BSTIterator that walks a binary search tree in in-order (increasing) order:
- BSTIterator(root) sets up the iterator for the tree rooted at root. Think of a pointer that starts just before the smallest value.
- hasNext() returns True if there is still a value to the right of the pointer.
- next() moves the pointer one step right and returns the value it now points at.
next() is only called when a value is left. Aim for next() and hasNext() in amortized O(1) time using O(h) memory, where h is the height of the tree.
Tests replay a call sequence: the first entry builds the iterator from the tree given as a level-order list (None marks a missing child), each later entry is a method call, and the constructor reports None. TreeNode, from_level() and to_level() are already defined.
Examples
Input: ops = ["BSTIterator","next","next","hasNext","next","hasNext"], args = [[[5,2,9]],[],[],[],[],[]] Output: [null,2,5,true,9,false]
The values come out as 2, 5, 9, after which nothing is left.
Input: ops = ["BSTIterator","hasNext","next","hasNext"], args = [[[4]],[],[],[]] Output: [null,true,4,false]
A single-node tree yields one value.
Input: ops = ["BSTIterator","next","next","hasNext","next","hasNext","next","next","hasNext"], args = [[[7,3,15,None,None,9,20]],[],[],[],[],[],[],[],[]] Output: [null,3,7,true,9,true,15,20,false]
The values come out as 3, 7, 9, 15, 20; hasNext() is True until the last one is read.
Constraints
- 1 <= number of nodes <= 10^5
- 0 <= Node.val <= 10^6
- At most 10^5 calls to hasNext and next
- next() is only called when a value is left
Approaches
- Baseline: flatten the tree in the constructor — time O(n) constructor, O(1) per call, space O(n)
Follow-up
The stack is the recursion of an in-order traversal, paused between values. A descending iterator is the mirror image (push right spines). The use cases put sorted order to work: the smallest gap between neighbors in one BST, and two iterators merging two BSTs.
Related problems
Start free on Cariara · Coding problems · System design studio
