⚡Flashcard Drill➔
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

  1. Keep an explicit stack representing the path to the next node.
  2. The constructor pushes the left spine of the root, so the top of the stack is the smallest value.
  3. next pops the top, then pushes the left spine of its right subtree -- which sets up the next smallest value.
  4. 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 None from next when exhausted: the contract assumes hasNext is 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems