Domain 2MediumCORE

Binary Search Tree Iterator

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 via hasNext(). Constraints:** We must achieve $O(1)$ average time per call and $O(h)$ space, where $h$ is tree height. This rules out storing all nodes in a list ($O(N)$ space) or traversing the whole subtree every time (next() takes too long).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Stack#Tree#Design

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 via hasNext().
  • Constraints: We must achieve O(1)O(1) average time per call and O(h)O(h) space, where hh is tree height. This rules out storing all nodes in a list (O(N)O(N) 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 O(N)O(N) memory for all elements upfront, violating the follow-up constraint.

To achieve O(1)O(1) 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.”

  1. When next() is called, we want the smallest available number (the left-most node).
  2. 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.

  1. 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).
  2. 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.
  3. 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: O(1)O(1) average for both next() and hasNext(). 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: O(h)O(h), where hh is the height of the tree. In a skewed BST (h=Nh=N), space is O(N)O(N). In a balanced BST (h=log⁡Nh=\log N), space is O(log⁡N)O(\log N). 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 O(N)O(N) 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 ≥1\ge 1, 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.