Binary Search Tree Iterator is a design-style problem that tests whether you understand both binary search trees and controlled traversal. You are given the root of a binary search tree and asked to implement an iterator that returns the next smallest number each time it is called.
The iterator must behave like an in-order traversal of the tree. That means values are returned in sorted order. You are not allowed to flatten the entire tree upfront into a list. Instead, you must return values incrementally, one at a time, as the iterator advances.
This problem appears frequently in interviews because it combines tree traversal, stack usage, and state management in a single, clean abstraction.
Why a naive solution is not enough
The simplest idea is to perform a full in-order traversal at the beginning and store all values in an array. Then each call to the iterator simply returns the next value from that array.
While this works logically, it uses extra memory proportional to the number of nodes. More importantly, it avoids the core challenge of the problem: producing values lazily, only when requested.
Interviewers want to see whether you can simulate recursion using an explicit data structure and maintain traversal state across multiple calls.
The key idea behind the solution
The correct mental model is this: you are pausing and resuming an in-order traversal.
In a recursive in-order traversal, the call stack naturally remembers where you are in the tree. Since recursion is not used here, you must recreate that behavior manually.
The data structure that allows you to do this is a stack.
Want to explore more coding problem solutions? Check out the Shortest Path in Binary Matrix and Swapping Nodes in a Linked List.
How the iterator works conceptually
When the iterator is initialized, you start at the root and push all left children onto the stack until you reach the leftmost node.
This ensures that the smallest element in the tree is always on top of the stack.
When next() is called, you pop the top node from the stack. That node’s value is the next smallest value.
If the popped node has a right child, you then move to that right child and push it and all of its left descendants onto the stack.
This process mirrors what recursion would do automatically in an in-order traversal.
The stack always contains the path to the next unvisited node.
Why this approach is correct
In a binary search tree, an in-order traversal visits nodes in ascending order.
By always pushing left children first, you guarantee that the smallest unvisited node is ready at the top of the stack.
When you move to a right subtree, pushing its leftmost path ensures correct ordering without revisiting nodes.
Each node is pushed onto the stack exactly once and popped exactly once.
How hasNext() fits in
The hasNext() operation is simple.
If the stack is not empty, there are still nodes left to visit, so hasNext() returns true.
If the stack is empty, the traversal is complete.
This check runs in constant time and does not modify any state.
Performance in simple terms
Initialization takes time proportional to the height of the tree.
Each call to next() runs in constant time on average, even though it may push several nodes occasionally.
Space usage is proportional to the height of the tree, not the total number of nodes.
This is efficient and meets typical interview constraints.
Common mistakes candidates make
One common error is forgetting to push all left descendants after moving to a right child.
Another is assuming the tree is balanced and misunderstanding worst-case space usage.
Some candidates also try to store all values upfront, which misses the intent of the problem.
Top comments (0)