173 · Binary Search Tree Iterator

Turn an in-order traversal into an object with next() and hasNext(), without ever materialising the full sequence. The trick is to freeze a recursive call stack in a plain array and thaw it one frame at a time.

1 — The problem

Implement BSTIterator over the root of a binary search tree so that calling next() repeatedly yields every value in ascending order, one at a time. hasNext() reports whether any values remain. Both methods are expected to run in average O(1) time and the whole structure in O(h) memory, where h is the tree's height — not O(n). That memory bound is the entire point of the exercise: it rules out the laziest correct solution.

The flatten approach is the one every candidate reaches for first, and it is disqualified by the O(h) requirement the moment the interviewer states it. The controlled-recursion approach below is the expected answer; Morris threading is the answer that gets a raised eyebrow.

2 — Visualizing the idea

2.1 The stack is the recursion

A textbook in-order traversal is inorder(l); visit(node); inorder(r);. Every recursive call pushes a frame; the frame currently paused on inorder(l) sits underneath the one that hasn't started yet. If you write that same idea iteratively, the call stack becomes an explicit Deque<TreeNode>: push a node, then push its way down the left spine, exactly the way recursion would have entered inorder(l) without ever visiting anything.

The constructor does this once for the root. From then on, every next() pops the top — the smallest value not yet returned — and, because that node's whole left subtree is already accounted for, pushes the left spine of its right child so the stack is ready for whatever comes next.

public int next() {    TreeNode node = stack.pop();    pushLeft(node.right);    return node.val;}private void pushLeft(TreeNode node) {    while (node != null) {        stack.push(node);        node = node.left;    }}

Watch the stack strip: it never holds more than the left spine below whatever's already been visited. Every node is pushed exactly once and popped exactly once across the whole traversal — which is precisely why the amortised cost per call is O(1) even though a single unlucky next() can walk an entire spine.

2.2 Reading the states

Because the stack only ever contains ancestors-via-left-turns, the top of the stack is always the smallest value the traversal hasn't produced yet — that invariant is the whole correctness argument, and it's worth pausing on each frame until it feels obvious.

3 — Complexity and the O(h) argument

• Space: O(h). The stack holds at most one node per level of the tree, restricted to the ones reached by left turns. For a balanced tree, h = O(log n). For a completely left-skewed tree the constructor's initial pushLeft(root) pushes every node, so the bound degrades to O(n) — the answer is still correctly stated as O(h), it's just that h itself can be as large as n in a degenerate tree.
• Time, amortised O(1) per call. Across the whole lifetime of the iterator every node is pushed once and popped once, so the total work over n calls to next() is O(n) — O(1) on average, even though any single call can cost O(h) if it has to push a long right-subtree spine.
• hasNext() is a stack-emptiness check: O(1), no amortisation needed.
• Edge cases: an empty tree gives an iterator that reports hasNext() == false immediately; a single-node tree pushes just the root; calling next() after exhaustion is undefined by the problem's contract — guard it in production code even though the visualiser (and most test suites) never do.

4 — Reference implementation

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

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

    public int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);
        return node.val;
    }

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

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

The visualiser above drives its frames from a direct JavaScript port of this exact class — the stack and the "returned so far" list you see are the real Deque after every push and pop, not a hand-drawn animation.