LeetCode 173 – Binary Search Tree Iterator

Binary Search Tree Iterator is inorder traversal split across two methods, and that is the entire insight. The loop that descends left becomes the "advance" step, the stack becomes the object's state, and a traversal turns into an iterator without a single new idea — which is exactly why it is worth doing after problem 94 rather than before.

The problem

Implement an iterator over a binary search tree:

• next() — return the next smallest value.
• hasNext() — whether any values remain.

The follow-up asks for O(1) average time and O(h) memory, where h is the tree's height.

      7
     / \
    3   15          next() -> 3
       /  \         next() -> 7
      9    20       hasNext() -> true
                    next() -> 9
                    next() -> 15
                    hasNext() -> true
                    next() -> 20
                    hasNext() -> false

"Next smallest" is ascending order, and inorder traversal of a BST is exactly ascending order — the property established in problem 94 and used in Validate BST. The problem is asking for that traversal, one value at a time.

The easy answer, and why the constraint rejects it

Flatten the whole tree into a list in the constructor, then hand out elements with an index. It is five lines and completely correct.

It is also O(n) memory and an O(n) constructor, and the follow-up asks for O(h) — O(log n) on a balanced tree. The distinction is real: an iterator that materialises everything up front is not an iterator, it is a list with extra steps, and it cannot start producing values before it has visited the whole tree.

Say it, name the trade, then do it lazily.

Lazy: the stack is the state

Problem 94's iterative traversal does two things in a loop — descend left pushing as it goes, then pop, emit, and turn right. Cut the loop in half:

constructor:  push the whole left spine from the root

next():       pop           <- the smallest remaining
              push the left spine of its RIGHT child
              return its value

hasNext():    is the stack non-empty

The stack always holds the ancestors of the next value that have not yet been emitted. That is the invariant, and it is worth stating: the top of the stack is always the next value to return. Everything else follows.

Java

class BSTIterator {
    // The stack holds exactly the not-yet-emitted ancestors of the next value,
    // so its top is always what next() should return.
    private final Deque<TreeNode> stack = new ArrayDeque<>();

    public BSTIterator(TreeNode root) {
        pushLeftSpine(root);
    }

    public int next() {
        TreeNode node = stack.pop();

        // Everything smaller in the right subtree comes before this node's ancestors.
        pushLeftSpine(node.right);

        return node.val;
    }

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

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

pushLeftSpine(node.right) handles a null right child without a guard — the loop simply does not run. That is why the helper takes a possibly-null node rather than the caller checking.

hasNext is a single stack test because the invariant guarantees the stack is empty exactly when the traversal is finished. No counter, no size field, nothing to keep in sync.

Python

class BSTIterator:
    def __init__(self, root: TreeNode):
        self.stack: list[TreeNode] = []
        self._push_left_spine(root)

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

    def hasNext(self) -> bool:
        return len(self.stack) > 0

    def _push_left_spine(self, node: TreeNode) -> None:
        while node:
            self.stack.append(node)
            node = node.left

A plain list is the right stack here — append and pop from the end are both O(1), and unlike level order there is no queue operation to worry about.

Why next() is O(1) average and not O(h)

A single next() can push an entire left spine, which is O(h) work. So the worst case for one call really is O(h) — the follow-up says average for a reason.

The amortised argument: across a full traversal, every node is pushed exactly once and popped exactly once. That is 2n operations spread over n calls to next(), so the average is O(1). An expensive call has just done work that several cheap calls will benefit from.

Being able to give that argument is what the problem is testing. "It's O(1)" without it is a claim; with it, it is an answer — and it is the same amortised reasoning behind the predecessor search in Flatten Binary Tree.

Complexity

The lazy version also starts returning values immediately, which matters if the consumer stops early — O(h) of work to produce the first element instead of O(n).

The follow-ups

Add prev(). A second stack for the mirror direction, kept in sync — harder than it sounds, because a next() has to invalidate part of the backward stack. Worth naming rather than attempting.

What if the tree is modified during iteration? The stack holds node references that may no longer be reachable. Java's collections answer this with fail-fast modification counters; saying so shows you have met the problem outside an interview.

Morris traversal gets the memory to O(1), using the threading trick from problem 94. It also mutates the tree while iterating, which makes it a poor fit for an iterator that a caller might abandon halfway — the threads would be left in place. That caveat is the interesting part.

What the interviewer is checking

• That you recognise this as inorder traversal, paused.
• That you offer the flatten-everything version and then reject it against the constraint.
• The invariant: the stack's top is always the next value.
• The amortised argument for O(1) average.
• That hasNext is just an empty check.
• An empty tree, and a tree that is a single left chain.
• That a lazy iterator can be abandoned early, and why that matters.