BST Iterator Design

Description

A caller wants a BST's values in sorted order, one at a time, through next() and hasNext(), and may stop after a few. Recursive inorder produces everything in one go and can't pause. Building the full sorted list works, but it costs O(n) even if the caller only wants three values. This skill builds an iterator that does only the work each call needs: an explicit stack that holds one path of the tree at a time.

We'll go from simple to more technical:

1. The pattern: an ascending iterator built on a stack of the left spine.
2. A second flavor: descending order, plus peek().
3. Where these iterators run in production (sorted maps, database cursors, generators).
4. What breaks it: forgotten right subtrees, a peek that advances, and precomputing everything.

The approach

class BSTIterator {
    private final Deque<TreeNode> stack = new ArrayDeque<>();

    BSTIterator(TreeNode root) { pushLeft(root); }

    private void pushLeft(TreeNode node) {
        while (node != null) { stack.push(node); node = node.left; }
    }

    boolean hasNext() { return !stack.isEmpty(); }

    int next() {
        TreeNode node = stack.pop();       // the smallest value not yet returned
        pushLeft(node.right);              // everything in its right subtree comes next, smallest first
        return node.val;
    }
}

class BSTIterator:
    def __init__(self, root: TreeNode | None):
        self.stack = []                  # a Python list is the stack: append / pop
        self.push_left(root)

    def push_left(self, node: TreeNode | None) -> None:
        while node is not None:
            self.stack.append(node)
            node = node.left

    def has_next(self) -> bool:
        return bool(self.stack)

    def next(self) -> int:
        node = self.stack.pop()          # the smallest value not yet returned
        self.push_left(node.right)       # everything in its right subtree comes next, smallest first
        return node.val

This is recursive inorder with the call stack made explicit and paused between calls. The stack holds the nodes whose left subtree is being (or has been) handled but whose own value hasn't been returned yet - the top is always the smallest value still pending. Popping it and pushing its right child's left spine is exactly the work recursion would do next.

A second flavor: descending, with peek

Mirroring left and right gives the values largest first: push the right spine, and after popping a node push its left child's right spine. Adding peek() - "what's next, without advancing" - is one line, because the next value is always on top of the stack:

class DescendingIterator {
    private final Deque<TreeNode> stack = new ArrayDeque<>();
    DescendingIterator(TreeNode root) { pushRight(root); }
    private void pushRight(TreeNode node) { for (; node != null; node = node.right) stack.push(node); }
    boolean hasNext() { return !stack.isEmpty(); }
    int peek() { return stack.peek().val; }                  // look, don't advance
    int next() { TreeNode node = stack.pop(); pushRight(node.left); return node.val; }
}

class DescendingIterator:
    def __init__(self, root: TreeNode | None):
        self.stack = []
        self.push_right(root)

    def push_right(self, node: TreeNode | None) -> None:
        while node is not None:
            self.stack.append(node)
            node = node.right

    def has_next(self) -> bool:
        return bool(self.stack)

    def peek(self) -> int:
        return self.stack[-1].val        # look, don't advance

    def next(self) -> int:
        node = self.stack.pop()
        self.push_right(node.left)
        return node.val

An ascending and a descending iterator together are the O(h)-space version of the two-pointer sweep (see Two Sum in a BST).

Where you'll see it

Every sorted-map iterator (TreeMap.keySet().iterator(), a database cursor scanning an index) works this way: it keeps just enough state to produce the next item and advances only when asked, so a caller that stops early pays only for what it read. The same "explicit stack, paused traversal" shape is what generators and lazy sequences compile down to. In Python you can write it as one - a recursive inorder(node) that does yield from inorder(node.left), yield node.val, yield from inorder(node.right) pauses at every yield - but a generator can't answer has_next() or peek() without pulling the next value early, which is why the explicit stack is still the interview answer.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A single next() call can push several nodes. Why is next() still O(1) amortized?

2. next() pops a node and returns it without pushing anything. On [7, 3, 15, null, null, 9, 20], what does the iterator produce?

3. What changes to make the iterator run in descending order?

Key takeaways

• A BST iterator is inorder traversal with the stack made explicit, advanced one value per next().
• Push the left spine; next() pops the top and pushes its right child's left spine.
• O(h) space; next() is amortized O(1) because every node is pushed and popped once.
• Mirror it (right spine, then the left child's right spine) for a descending iterator; peek() is just the top of the stack.
• Precomputing the list gives O(1) per call but O(n) space and up-front work - wasteful when the caller stops early.