150. Binary Search Tree Iterator

A recursive in-order traversal visits nodes in sorted order, but we can't pause a recursion between calls. So we make the recursion explicit with a stack: the stack always holds the chain of ancestors whose values still need to be returned. Its top is always the next value in sorted order, so next() is a pop plus a small fix-up, and hasNext() is just 'is the stack non-empty?'.

Why a stack

In-order traversal of a BST (left, node, right) yields values in ascending order. A normal recursion produces them all at once; an iterator must hand them out one at a time, on demand. The fix is to simulate the recursion's call stack ourselves and freeze it between next() calls.

The invariant

We keep a stack that, at every moment, holds exactly the nodes whose left subtrees have already been fully accounted for and whose values have not yet been returned — with the smallest such value on top. Concretely, the stack holds a node plus all of its left-spine ancestors.

We maintain it with one helper, pushLeft(node): starting at node, push it and keep walking left, pushing every node, until you fall off the tree. This stacks up the leftmost path — and the leftmost node (the smallest value in that subtree) ends up on top.

The operations

• Constructor: call pushLeft(root). Now the global minimum sits on top.
• next(): pop the top node n (it's the next in-order value). Before returning n.val, its right subtree now becomes eligible, so call pushLeft(n.right) to stack that subtree's left spine. Return n.val.
• hasNext(): return whether the stack is non-empty.

Worked example: root = [7,3,15,null,null,9,20]

The BST has 7 at the root, 3 on the left, and 15 → (9, 20) on the right. In-order order is 3, 7, 9, 15, 20.

Why the amortized cost is O(1)

A single next() can push a whole left spine, which looks like O(h). But each node is pushed exactly once and popped exactly once over the iterator's entire life. Across n calls the total work is O(n), so next() averages O(1). The stack never holds more than one root-to-leaf path, so memory is O(h).

Complexity

• Time: O(1) amortized per next()/hasNext().
• Space: O(h) for the stack, where h is the tree height.

import java.util.*;

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

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

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

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

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