BST Iterator
Iterator over a BST's inorder sequence: next() and hasNext() in amortized O(1), O(h) memory.
- The number of nodes in the tree is in the range [1, 10⁵].
- 0 <= Node.val <= 10⁶
- At most 10⁵ calls will be made to hasNext, and next.
Intuition
A binary search tree iterator exposes a BST's sorted order one value at a time through next() and hasNext(). The easy version — run a full inorder traversal in the constructor, store all n values in a list, and hand them out — meets the interface but fails the space requirement: it costs O(n) memory, and on a tree that does not fit in memory it is useless before it starts.
The requirement is O(h) space, where h is the height. That number is a strong hint: h is exactly how much state a paused inorder traversal needs. A recursive inorder holds at most h frames on the stack at any moment. So instead of running the traversal to completion, freeze it — keep only the stack it would have had, and resume when next() is called.
What is on that stack has a clean meaning:
- The nodes whose left subtrees are fully processed, but which have not been emitted yet.
That is the left spine of the current position. next() pops the top — the smallest unvisited value — and then pushes the left spine of that node's right subtree, since those values come next in sorted order. Each node is pushed exactly once and popped exactly once across the iterator's whole life, so n calls to next() cost O(n) in total, which is amortised O(1) per call even though one individual call may push h nodes.
A paused inorder traversal — the shape any bst iterator takes. The stack holds exactly the left spine — the nodes whose values are still pending — so next() pops one and pushes the spine of its right child. Space is O(h), not O(n), because only one root-to-node path is ever stored.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for amortized O(1) time and O(h) space.
Store the traversal's state, not its output
The constructor pushes the left spine from the root: push the node, move left, repeat until null. The stack now holds the path to the smallest value, with that value on top. O(h) space, not O(n) — this is the whole point of the design.
next() pops the smallest remaining value
The top of the stack is always the next value in sorted order, because everything smaller has already been emitted and everything on the stack is an unvisited ancestor. Pop it and hold it as the return value.
After popping, push the right subtree's left spine
A popped node's left subtree and the node itself are now finished, so the following values live in its right subtree. Move to node.right and push its left spine using the same loop as the constructor. If there is no right child, push nothing — the stack already holds the correct next node.
hasNext() is just a non-empty check
Values remain exactly when the stack is non-empty, so this is a single O(1) test. No lookahead and no counter are needed, because the stack already encodes whether the traversal is finished.
Reuse one spine-pushing helper
The constructor and next() perform the identical operation — push a node and every left descendant. Factoring it into one helper removes the most common source of bugs in this problem, which is the two copies drifting apart.
Why the amortised bound holds
Each node enters the stack once and leaves once over the iterator's entire lifetime, so n calls do O(n) work in total. A single next() can push up to h nodes, but that expense is paid back by the cheap pops that follow. Worst-case O(h) per call, amortised O(1), with space never exceeding O(h).
Solution & live demo
Common pitfalls
Flattening the whole tree in the constructor
self.vals = inorder(root) self.i = 0
self.stack = [] self._spine(root)
Correct and often accepted, but it's O(n) memory and does all the work up front. The stack version uses O(h) and amortises the traversal across the calls that actually happen.
Pushing the right child rather than its spine
if node.right:
self.stack.append(node.right)self._spine(node.right)
The right child's own left descendants come before it in inorder. Pushing just the child returns it too early, emitting values out of order.
Descending right in the initial spine
while node:
self.stack.append(node)
node = node.rightwhile node:
self.stack.append(node)
node = node.leftInorder starts at the leftmost node. Following right pointers seeds the stack with the largest values, so the iterator returns the tree in roughly reverse order.
Edge cases
Stack holds one node at a time; each next() pushes the next chain node.
hasNext() false guards; next() on empty is undefined by contract.