Binary Search Tree Iterator
Problem
Implement an iterator over a binary search tree (BST) that returns the nodes' values in ascending order using next() and hasNext() methods.
- 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 next() and hasNext()
Example
root = [7,3,15,null,null,9,20][3,7,9,15,20]Insight: The iterator never searches for the next value directly. Instead, it maintains a frontier where the next smallest node is always either reachable by moving left from cur, or already waiting on top of stack. Meaning of state: cur points to the next subtree that still needs exploration. stack stores nodes that have been seen, but cannot be returned yet because smaller nodes may still exist under their left side. The top of stack is the rightmost element. Rule of next(): If cur is not null, the iterator pushes cur and repeatedly moves left until cur becomes null. Once cur is null, the iterator pops the top node, returns its value, and then moves to its right subtree by setting cur to node.right. The input is root = [7,3,15,null,null,9,20]. next() call 1: Before: cur = 7, stack = []. The iterator pushes 7 and sets cur to 3. The iterator pushes 3 and sets cur to null. The iterator pops 3, returns 3, and sets cur to 3.right, which is null. After: cur = null, stack = [7]. next() call 2: Before: cur = null, stack = [7]. Because cur is null, the next smallest node is already on top of the stack. The iterator pops 7, returns 7, and sets cur to 7.right, which is 15. After: cur = 15, stack = []. next() call 3: Before: cur = 15, stack = []. The iterator pushes 15 and sets cur to 9. The iterator pushes 9 and sets cur to null. The iterator pops 9, returns 9, and sets cur to 9.right, which is null. After: cur = null, stack = [15]. next() call 4: Before: cur = null, stack = [15]. Because cur is null, the next smallest node is already on top of the stack. The iterator pops 15, returns 15, and sets cur to 15.right, which is 20. After: cur = 20, stack = []. next() call 5: Before: cur = 20, stack = []. The iterator pushes 20 and sets cur to null. The iterator pops 20, returns 20, and sets cur to 20.right, which is null. After: cur = null, stack = [].
Approach
Straightforward Solution
A naive approach is to perform a full inorder traversal upfront, storing all node values in a list, and then iterate over this list. This requires O(n) space and upfront O(n) time, which is inefficient for large trees or partial iteration.
Core Observation
Inorder traversal of a BST yields nodes in ascending order. To iterate without recursion, a stack can simulate the traversal by pushing left children until none remain, then processing nodes and moving to right children.
Path to Optimal
The key insight is to simulate inorder traversal lazily using a stack that stores the path to the current node. Instead of storing all nodes, the iterator maintains a stack of nodes whose left subtrees have been fully explored but whose right subtrees are yet to be visited. This allows next() to run in average O(1) amortized time and uses O(h) space, where h is the tree height.
Optimal Approach
Initialize the iterator with the root node as the current pointer and an empty stack. The hasNext() method returns true if either the current pointer is not null or the stack is not empty. The next() method pushes all left descendants of the current node onto the stack, then pops the top node from the stack, sets the current pointer to its right child, and returns the popped node's value. This simulates inorder traversal on demand without recursion or full upfront traversal.
Time
O(1) amortized per next() call
Each node is pushed and popped exactly once from the stack across all calls, so the total work is O(n). Spread over n calls, each next() runs in O(1) amortized time.
Space
O(h)
The stack stores at most one path from the root to a leaf, which is bounded by the height h of the tree. This is optimal for inorder traversal simulation without full traversal storage.
Pattern Spotlight
DFS (Controlled Inorder Traversal with Stack)
To iterate over a BST in ascending order without recursion, maintain a stack of nodes representing the path to the current node, pushing left children until none remain, then process nodes and move to right children, ensuring O(h) space and amortized O(1) next() time.
Solution
| 1 | class BSTIterator: |
| 2 | def __init__(self, root): |
| 3 | self.cur = root |
| 4 | self.stack = [] |
| 5 | |
| 6 | def hasNext(self): |
| 7 | return bool(self.cur) or bool(self.stack) |
| 8 | |
| 9 | def next(self): |
| 10 | while self.cur is not None: |
| 11 | self.stack.append(self.cur) |
| 12 | self.cur = self.cur.left |
| 13 | |
| 14 | node = self.stack.pop() |
| 15 | self.cur = node.right |
| 16 | return node.val |
Step-by-Step Solution
Initialize Iterator State with Root and Empty Stack
| 3 | self.cur = root |
| 4 | self.stack = [] |
Objective
To set up the iterator's internal state by storing the current node pointer and initializing an empty stack for traversal.
Key Insight
Storing the current node pointer allows the iterator to track the traversal progress lazily. The stack will hold nodes whose left subtrees have been traversed but whose right subtrees are pending. This setup enables controlled DFS without recursion, maintaining O(h) space.
Interview Quick-Check
Core Logic
The current pointer tracks the next node to explore, while the stack stores the path of nodes waiting to be processed.
Common Pitfalls & Bugs
Failing to initialize the stack or current pointer correctly can cause incorrect traversal order or runtime errors.
Determine Availability of Next Node with hasNext()
| 6 | def hasNext(self): |
| 7 | return bool(self.cur) or bool(self.stack) |
Objective
To check if the iterator has more nodes to return by verifying if the current pointer or stack is non-empty.
Key Insight
If the current pointer is not null, there are still nodes to explore down the left subtree. If the stack is not empty, there are nodes previously visited whose right subtrees are yet to be traversed. Checking both ensures accurate detection of remaining nodes.
Interview Quick-Check
Core Logic
hasNext() returns true if either the current pointer or the stack contains nodes to process, reflecting the traversal state.
State & Boundaries
The method must consider both current and stack states to avoid prematurely signaling traversal completion.
Advance Iterator by Traversing Left Subtree and Returning Next Node
| 10 | while self.cur is not None: |
| 11 | self.stack.append(self.cur) |
| 12 | self.cur = self.cur.left |
| 14 | node = self.stack.pop() |
| 15 | self.cur = node.right |
| 16 | return node.val |
Objective
To simulate inorder traversal by pushing all left descendants onto the stack, popping the next node, and moving to its right subtree.
Key Insight
Pushing all left children ensures the smallest unvisited node is on top of the stack. Popping this node returns the next smallest value. Setting the current pointer to the popped node's right child prepares the iterator to explore the right subtree on subsequent calls. This controlled DFS approach avoids recursion and full traversal storage.
Interview Quick-Check
Core Logic
next() pushes left children to reach the next smallest node, pops it, then shifts focus to its right subtree, maintaining inorder traversal order.
State & Boundaries
The while loop continues until no more left children remain, ensuring the stack top is the next node to return.
Common Pitfalls & Bugs
Not updating the current pointer to the right child after popping leads to incorrect traversal and missed nodes.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
while self.cur is not None:Traverse left subtree by pushing current nodes onto the stack.
Pushing all left descendants ensures the next smallest node is on top of the stack, preserving inorder traversal order without recursion.
node = self.stack.pop()Pop the top node from the stack as the next node to return.
Popping retrieves the next smallest node whose left subtree has been fully explored, maintaining correct traversal order.
self.stack = []Initialize an empty stack to store nodes during traversal.
The stack is essential for simulating recursion and tracking nodes whose left subtrees have been visited but right subtrees remain, enabling controlled DFS.
def hasNext(self):Check if there is a next node by verifying current pointer or stack is non-empty.
This condition accurately reflects whether the traversal has remaining nodes to visit, ensuring hasNext() returns true only when more nodes exist.
self.stack.append(self.cur)Push the current node onto the stack before moving left.
Storing the current node preserves the path for backtracking after left subtree exploration, enabling correct traversal sequencing.
self.cur = node.rightSet current pointer to the right child of the popped node.
Moving to the right child prepares the iterator to explore the right subtree next, continuing inorder traversal correctly.
self.cur = rootAssign the root node to the current pointer to start traversal.
Setting the current pointer to root initializes the traversal state, enabling the iterator to begin exploring the BST from the top.
self.cur = self.cur.leftMove current pointer to the left child to continue traversal.
Descending left aligns with inorder traversal's left-root-right order, ensuring nodes are visited in ascending order.
return node.valReturn the value of the popped node as the next smallest element.
Returning the popped node's value completes the next() operation, delivering the correct inorder sequence element.
return bool(self.cur) or bool(self.stack)Return boolean indicating if next node exists.
Returning the boolean result of the condition provides a simple and efficient way to signal traversal progress.
Test Your Understanding
Why does the iterator push all left children onto the stack before popping a node in next()?
Because inorder traversal visits left subtree nodes before the current node, pushing all left children ensures the next smallest node is on top of the stack, enabling correct ascending order iteration.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Binary Search Tree Iterator from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Binary Search Tree Iterator drill