Binary Search Tree Iterator: Controlled Inorder with a Stack
You are given the root of a binary search tree. Implement the BSTIterator class with two methods: next() returns the next smallest element in the BST, and hasNext() returns true if there are still elements to visit. Both operations should run in O(1) average time, and the iterator should use O(h) memory where h is the height of the tree.
This is LeetCode 173: Binary Search Tree Iterator. It asks you to turn a recursive inorder traversal into a lazy, on-demand iterator. Instead of collecting all values up front, you yield them one at a time using a stack.
Example: for the BST [7, 3, 15, null, null, 9, 20], calling next() repeatedly produces 3, 7, 9, 15, 20.
The core idea
An inorder traversal of a BST visits nodes in sorted order. The iterative version uses a stack and a "push all left children" loop. This problem asks you to split that loop across multiple next() calls instead of running it all at once.
The trick is to only push the left spine of the current subtree. When you pop a node, you process it (return its value), then push the left spine of its right child. This way the stack never holds more than O(h) nodes at any time.
Here is the full approach:
- Constructor: start at the root and push every left child onto the stack until you reach a node with no left child. The top of the stack is now the smallest element.
next(): pop the top node. That is the next smallest value. If the popped node has a right child, push that right child and then all of its left descendants onto the stack. Return the popped value.hasNext(): return whether the stack is non-empty.
Python solution
class BSTIterator:
def __init__(self, root):
self.stack = []
self._push_left(root)
def next(self):
node = self.stack.pop()
self._push_left(node.right)
return node.val
def hasNext(self):
return len(self.stack) > 0
def _push_left(self, node):
while node:
self.stack.append(node)
node = node.left
The helper _push_left encapsulates the "push the left spine" logic. The constructor calls it on the root. Each next() call pops one node and calls it on the right child. That is the entire implementation.
This is exactly the iterative inorder traversal pattern from LeetCode 94, but broken into pieces. The inner while curr loop that pushes left children becomes _push_left. The pop and curr = curr.right step becomes next(). If you already know iterative inorder, you already know this solution.
Walkthrough: stack state after each next() call
Starting from the BST [7, 3, 15, null, null, 9, 20], the constructor pushes the left spine: first 7, then 3. The stack is [7, 3] with 3 on top. Let's trace each next() call.
next() call 1: Pop 3. No right child. Return 3.
Pop 3 from the stack. Node 3 has no right child, so nothing new gets pushed. Stack: [7].
next() call 2: Pop 7. Push right child 15, then its left spine (9). Return 7.
Pop 7. It has right child 15. Push 15, then go left to 9. Push 9. Node 9 has no left child, so stop. Stack: [15, 9].
next() call 3: Pop 9. No right child. Return 9.
Pop 9. Node 9 has no right child, so nothing gets pushed. Stack: [15].
next() call 4: Pop 15. Push right child 20. Return 15.
Pop 15. It has right child 20. Push 20. Node 20 has no left child, so stop. Stack: [20].
next() call 5: Pop 20. No right child. Stack empty. Return 20.
Pop 20. No right child. Stack is empty. hasNext() would now return False. All nodes visited in sorted order.
Notice how the stack never holds more than 2 nodes at any point during this traversal. The height of this tree is 3, and the stack stays within O(h) space.
Complexity analysis
| Operation | Time | Space |
|---|---|---|
| Constructor | O(h) | O(h) |
next() | O(1) amortized | O(h) |
hasNext() | O(1) | O(1) |
Time for next() is O(1) amortized, not O(1) worst case. A single next() call might push up to h nodes onto the stack (when the popped node has a right child with a deep left spine). But across all n calls to next(), every node gets pushed exactly once and popped exactly once. That is 2n total operations spread over n calls, giving O(1) amortized per call.
Space is O(h) where h is the height of the tree. The stack holds at most one path from root to leaf at any time. For a balanced BST, h = log(n). For a completely skewed tree, h = n.
Edge cases
- Single node: the constructor pushes the root. The first
next()pops it and returns its value._push_left(None)does nothing.hasNext()returnsFalseafter one call. - Left-only tree (every node only has a left child): the constructor pushes all n nodes onto the stack. Each
next()call simply pops one node with no right child. The stack shrinks by one each time. Space is O(n) since h = n for a skewed tree. - Right-only tree (every node only has a right child): the constructor pushes only the root (no left children to follow). Each
next()pops one node and pushes its right child (which also has no left child). The stack never holds more than one node. Space is O(1).
The building blocks
This problem is built on two reusable building blocks:
1. Iterative inorder traversal. The while curr or stack pattern with "push left, pop, go right" is the foundation of this iterator. You split the loop so that each iteration corresponds to one next() call. If you can write iterative inorder from memory, converting it into an iterator is a small step.
2. Lazy left-spine pushing. Instead of traversing the entire tree up front, you push only the left spine of the current subtree. When you pop a node and it has a right child, you push that child's left spine. This lazy approach is what keeps the memory at O(h) instead of O(n). The same technique appears in problems like Kth Smallest Element in a BST, where you want to stop the inorder traversal early after finding the kth value.
Both blocks appear frequently in BST problems. The iterative inorder pattern is the more general one. The lazy left-spine pushing is a specialization you use when you need on-demand traversal instead of collecting all results at once.
From understanding to recall
You now see how the BST iterator is just an iterative inorder traversal split across multiple method calls. The constructor pushes the left spine. Each next() pops, pushes the right child's left spine, and returns the value. hasNext() checks if the stack is non-empty.
But in an interview, you need to write this without any reference. You need to recall that the constructor calls _push_left(root), that next() pops and calls _push_left(node.right), and that the helper walks left until None. These are small details, but forgetting any one of them means a broken solution.
Spaced repetition turns understanding into automatic recall. You type the BSTIterator class from scratch after one day, then three days, then a week. Each time, you reconstruct the stack initialization, the next() logic, and the _push_left helper from memory. After a few rounds, the pattern is second nature. You stop thinking about how the iterator works and just write it.
The two building blocks here (iterative inorder and lazy left-spine pushing) are worth drilling independently. They transfer directly to Kth Smallest in BST, Validate BST, and any problem where you need controlled, step-by-step BST traversal.
Related posts
- Binary Tree Inorder Traversal - The iterative stack-based inorder pattern that this iterator is built on
- Validate Binary Search Tree - Uses inorder traversal of a BST to check sorted order, the same core property this iterator relies on