Binary Search Tree Iterator
Last Updated: March 29, 2026
Understanding the Problem
We need to build an iterator that walks through a BST in sorted order, one element at a time. Each call to next() should return the next smallest value, and hasNext() should tell us if there are more values remaining.
The interesting challenge here is the word "iterator." We can't just do an in-order traversal all at once, we need to pause and resume it on demand. Every time the caller asks for the next element, we hand them one value and then freeze our state until they ask again.
The BST property gives us a nice guarantee: an in-order traversal (left, root, right) visits nodes in ascending order. So the real question becomes: how do we implement a pausable in-order traversal?
Key Constraints:
Number of nodes up to 10^5--> The tree can be large. We need to be mindful of memory, especially if we're storing all nodes upfront.At most 10^5 calls to hasNext and next--> Each call needs to be efficient. O(h) or O(1) per call is ideal.0 <= Node.val <= 10^6--> Non-negative values, no special handling needed.
Approach 1: Flatten to Array
Intuition
The most direct approach is to separate the traversal from the iteration. We do a complete in-order traversal of the BST during construction, storing every value in a list. After that, next() just returns the next element from the list, and hasNext() checks if we've reached the end.
This is the "do all the work upfront" strategy. It's simple and it works, but it uses O(n) space to store every node's value. For the follow-up constraint of O(h) space, we'll need something smarter. But as a starting point, this is solid.
Algorithm
- In the constructor, perform an in-order traversal of the BST and store all values in a list.
- Maintain an index pointer starting at 0.
- For
next(), return the value at the current index and increment the index. - For
hasNext(), return true if the index is less than the list size.
Example Walkthrough
Code
- Time Complexity: O(n) for construction where n is the number of nodes, since we traverse the entire tree. O(1) for each
next()andhasNext()call, since we're just indexing into an array. - Space Complexity: O(n) to store every node's value in the list, on top of the O(h) recursion stack during construction.
This approach works but stores the entire tree's values upfront. Can we use only O(h) space by doing the in-order traversal incrementally, one node at a time?
Approach 2: Controlled Recursion with Stack (Optimal)
Intuition
If you've ever written an iterative in-order traversal, you know it uses a stack. You push all left children to get to the smallest element, then pop, process, and move to the right subtree. The trick for the iterator is that we don't run this loop to completion. We run it one step at a time.
Think of it this way: in a standard iterative in-order traversal, the stack always holds the "path of ancestors we haven't finished processing yet." At any moment, the top of the stack is the next node to return. After we pop and return that node, we push its right child's leftmost path onto the stack to set up for the next call.
So the constructor pushes all left children of the root (this gets us to the smallest element). Each next() call pops the top node, and if that node has a right child, pushes all left children of the right child. The stack always contains exactly the nodes we'll visit next, in the right order.
The beautiful thing is that the stack never holds more than O(h) nodes at once, because it only contains one node per level of the tree. This is exactly what the follow-up asks for.
The stack simulates the call stack of a recursive in-order traversal. In a recursive version, when you visit a node's left subtree, the current node stays on the call stack waiting to be processed. Here, we're doing the same thing explicitly: pushing nodes onto our own stack as we go left, then popping them when it's their turn.
The pushLeftBranch helper is the key operation. It takes any node and pushes it along with all its left descendants. This always puts the next smallest unvisited node on top of the stack. When we pop a node and it has a right subtree, that right subtree's leftmost path contains the next values in sorted order, so we push those too.
Algorithm
- In the constructor, initialize an empty stack. Push the root and all its left descendants onto the stack (this navigates to the smallest element).
- For
next(): - Pop the top node from the stack (this is the next smallest value).
- If the popped node has a right child, push the right child and all of its left descendants onto the stack.
- Return the popped node's value.
- For
hasNext(), return true if the stack is not empty.
Example Walkthrough
Code
- Time Complexity: O(n) for construction in the worst case. For
next(), each call is O(h) worst case but O(1) amortized because each node is pushed and popped exactly once across all calls.hasNext()is O(1). - Space Complexity: O(h) where h is the height of the tree. The stack never holds more than h nodes. For a balanced BST, h = O(log n). For a skewed tree, h = O(n).