170. Binary Search Tree Iterator
You are handed the root of a binary search tree and must serve its values back in ascending order, one at a time — the way an iterator would.
Implement a class BSTIterator with three pieces:
- the constructor receives the root of the BST;
next()returns the smallest value that has not been handed out yet;hasNext()reports whether any values remain.
next() is only ever called while at least one value remains. The judge builds the tree, constructs one iterator, then drives it with a sequence of next / hasNext calls and checks every answer.
Flattening the whole tree up front works — but the sharper design answers each call in amortized O(1) time while holding only O(h) memory, where h is the tree's height.
Example 1:
Input: BSTIterator(root of [7, 3, 15, null, null, 9, 20]); next(), next(), hasNext(), next(), next(), next(), hasNext()
Output: 3, 7, true, 9, 15, 20, false
Explanation: The in-order (ascending) sequence of this tree is 3, 7, 9, 15, 20. The two next calls yield 3 and 7; hasNext is true with 9, 15, 20 still pending; three more next calls drain them; the final hasNext is false.
Example 2:
Input: BSTIterator(root of [1]); hasNext(), next(), hasNext()
Output: true, 1, false
Explanation: A single-node tree: hasNext is true before the value is taken, next returns 1, and afterwards nothing remains.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- 0 ≤ Node.val ≤ 10⁶
- All node values are distinct and the tree is a valid BST.
- next is called only while a value remains.
- At most 2 × 10⁴ calls are made to next and hasNext combined.
Hints:
An in-order traversal of a BST visits values in ascending order. The easiest correct iterator does the whole traversal in the constructor and then just walks an array.
To get down to O(h) memory, pause the traversal instead of finishing it: keep an explicit stack holding the path of left children from the root — the top of that stack is always the next value.
When you pop a node to serve next(), push the left spine of its right child. Every node is pushed and popped exactly once overall, so next() is amortized O(1).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [7, 3, 15, null, null, 9, 20]; calls: next, next, hasNext, next, next, next, hasNext
Expected output: 3, 7, true, 9, 15, 20, false