Binary Search Tree Iterator

Binary Search Tree Iterator

What is this problem about?

The "Binary Search Tree Iterator interview question" is a design challenge. You are given the root of a Binary Search Tree (BST) and you need to implement an iterator that returns the values of the tree in in-order (sorted) sequence. The iterator must support two methods: next() (returns the next smallest number) and hasNext() (returns true if a next number exists).

Why is this asked in interviews?

Companies like Meta, Amazon, and LinkedIn use the "Binary Search Tree Iterator coding problem" to test a candidate's knowledge of Tree Traversal and State Management. Unlike a simple recursive traversal, an iterator must "pause" and "resume" its progress. It requires you to simulate the call stack using a real stack data structure.

Algorithmic pattern used

This problem uses the Stack-based In-order Traversal pattern.

1. Initialization: Use a stack to store nodes. From the root, push all "left" children onto the stack until you reach the smallest element.
2. next():
   • Pop the top node from the stack. This is the next smallest value.
   • If this node has a right child, move to the right child and then push all its "left" descendants onto the stack.
   • Return the popped node's value.
3. hasNext(): Simply check if the stack is empty.

Example explanation

BST: 7 is root, 3 is left child, 15 is right child. 15 has 9 (left) and 20 (right).

1. Init: Stack = [7, 3].
2. next(): Pop 3. Stack = [7]. Return 3.
3. next(): Pop 7. 7 has a right child (15).
   • Go to 15, then its left child (9). Stack = [15, 9]. Return 7.
4. next(): Pop 9. Stack = [15]. Return 9.
5. next(): Pop 15. 15 has a right child (20). Stack = [20]. Return 15.

Common mistakes candidates make

• Pre-calculating everything: Using a DFS to store all elements in a list during initialization. This uses $O(N)$ memory immediately, whereas the stack approach uses only $O(H)$ (height of the tree).
• Incorrect Stack Logic: Forgetting to process the right child's left-side branch in the next() method.
• Ignoring Space Constraints: The goal is usually to achieve $O(H)$ space and $O(1)$ average time per operation.

Interview preparation tip

Iterative tree traversal is a common "Design interview pattern." If you can explain why a stack is used to replace recursion, you show a strong understanding of how the computer manages function calls. Practice this alongside "Iterative DFS" and "BFS."