How do you solve Binary Search Tree Iterator?

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.

Binary Search Tree Iterator

Q: What is the time complexity of Binary Search Tree Iterator?

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.

Q: What pattern does Binary Search Tree Iterator use?

The Pattern: DFS (Controlled Inorder Traversal with Stack) The Heuristic: 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.

Medium DFS

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

Input: root = [7,3,15,null,null,9,20]

Output: [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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

1class BSTIterator:
def __init__(self, root):
self.cur = root
self.stack = []
5
def hasNext(self):
return bool(self.cur) or bool(self.stack)
8
def next(self):
while self.cur is not None:
	self.stack.append(self.cur)
	self.cur = self.cur.left
13
node = self.stack.pop()
self.cur = node.right
return node.val

Step-by-Step Solution

Initialize Iterator State with Root and Empty Stack

3self.cur = root
4self.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()

To check if the iterator has more nodes to return by verifying if the current pointer or stack is non-empty.

Advance Iterator by Traversing Left Subtree and Returning Next Node

To simulate inorder traversal by pushing all left descendants onto the stack, popping the next node, and moving to its right subtree.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 10 Critical

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.

Line 14 Critical

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.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why does the iterator push all left children onto the stack before popping a node in next()?

See the answer with Pro.

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

or drill a free problem

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`