NeetCode #457LC-173MediumTrees
← Back to All Problems#457 · #173 · Binary Search Tree Iterator(二叉搜索树迭代器)
📌 Problem Statement & Constraints
Implement a
BSTIterator over the in-order traversal of a binary search tree, supporting next() (the next smallest value) and hasNext(). Both should run in O(1) average time and use O(h) memory. Constraints: the number of nodes is in [1, 10^5]; at most 10^5 calls.💡 Core Algorithmic Approaches
- Keep an explicit stack representing the path to the next node.
- The constructor pushes the left spine of the root, so the top of the stack is the smallest value.
nextpops the top, then pushes the left spine of its right subtree -- which sets up the next smallest value.- The amortised cost is O(1) per call, since each node is pushed and popped once over the whole traversal.
💻 Benchmark Python3 Implementation
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.st = []
self._push_left(root)
def _push_left(self, node: Optional[TreeNode]) -> None:
while node:
self.st.append(node) # the left spine
node = node.left
def next(self) -> int:
node = self.st.pop() # smallest remaining
self._push_left(node.right) # set up the next one
return node.val
def hasNext(self) -> bool:
return bool(self.st)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) amortised per call, O(h) for the constructor.
💾 Space Complexity
O(h) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Materialising the whole in-order traversal in the constructor: O(n) time and space, violating the O(h) memory requirement.
- Forgetting to push the right subtree's left spine in
next: the iteration would stop after the left spine is exhausted. - Returning
Nonefromnextwhen exhausted: the contract assumeshasNextis checked first. - Using recursion to find the next node: that would be O(h) per call rather than amortised O(1).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.