173. Binary Search Tree Iterator
Model: qwen3.5:9b
Topics: Stack,Tree,Design
FAANG asked: 1
Acceptance rate: 60.6%
Problem Breakdown
We need an iterator that yields elements of a Binary Search Tree (BST) in sorted order (in-order traversal). The key requirement is lazy evaluation: we shouldn’t traverse the entire tree upfront during initialization if possible, and next()/hasNext() should be fast.
- Inputs: Root node of a BST (
TreeNode). - Outputs: Sorted integer values one by one via
next(), boolean status for remaining elements viahasNext(). - Constraints: We must achieve average time per call and space, where is tree height. This rules out storing all nodes in a list ( space) or traversing the whole subtree every time (
next()takes too long).
Intuition
A naive approach would be to perform an iterative DFS (in-order traversal), store results in a queue/list, and pop from it. However, that uses memory for all elements upfront, violating the follow-up constraint.
To achieve time per call with minimal space, we need to simulate recursion using a stack without storing every node permanently if not needed. In an in-order traversal (Left -> Root -> Right), when we visit a node’s left child, that path is “pending” until we return from the right side of that subtree. The key insight: The stack will hold exactly those nodes whose right children have been visited or are currently being processed but haven’t yielded their value yet. Specifically, it holds the current “left spine.”
- When
next()is called, we want the smallest available number (the left-most node). - If that node has a right child, all nodes in its right subtree’s left path become candidates for future calls and must be pushed onto our stack to maintain order.
Approach
We use an explicit stack to manage the traversal state during initialization and subsequent next() calls.
-
Constructor (
__init__):- Start at
root. While current node is not null, push it onto the stack and move left (curr = curr.left). - This initializes the iterator to point to the smallest element (the bottom of the left spine).
- Start at
-
Method
next():- Pop the top node from the stack; this is our current value.
- If that popped node has a right child, we must process its subtree next in-order. We move down to the far-left of that right child and push those nodes onto the stack until null (just like initialization).
- Return the popped value.
-
Method
hasNext():- Simply check if the stack is empty. If it’s not, there are elements remaining in our traversal path or pending left-spines of right subtrees.
Complexity Analysis
- Time: average for both
next()andhasNext(). Each node is pushed onto the stack exactly once (when its parent is visited) and popped exactly once (when it becomes the current minimum). The amortized cost per call is constant because we only traverse edges that haven’t been traversed before. - Space: , where is the height of the tree. In a skewed BST (), space is . In a balanced BST (), space is . This fits the requirement perfectly.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BSTIterator:
def __init__(self, root: TreeNode):
# Stack to store the path of nodes whose right children
# haven't been fully traversed yet. Top is always the smallest available value.
self.stack = []
curr = root
while curr:
self.stack.append(curr)
curr = curr.left
def next(self) -> int:
node = self.stack.pop() # Get current minimum
if node.right:
# If there is a right child, traverse its left spine
# and push those nodes onto the stack for future calls.
curr = node.right
while curr:
self.stack.append(curr)
curr = curr.left
return node.val
def hasNext(self) -> bool:
return len(self.stack) > 0
Edge Cases Handled
- Single Node Tree: Constructor pushes root,
next()pops it (no right child), returns value. Correct. - Skewed BST (Left-heavy): Stack grows to depth in constructor or during traversal logic; handled by stack structure naturally without overflow issues for standard recursion limits if implemented iteratively as shown.
- Empty Tree: Constraints specify nodes , but
hasNext()correctly returns False immediately on empty tree (if allowed). Code handles null root gracefully via loop condition in constructor. - Right-heavy Subtrees: When a node is popped, its right child’s left spine is pushed onto the stack before returning value to caller logic or subsequent calls; ensures correct order without re-traversal.