Binary Search Tree Iterator

MediumTrees · BST · Design (Controlled In-order)🧩 Binary Search Tree & In-order LeetCode #173 ↗Updated Oct 30, 2026

Problem

Design a class BSTIterator that walks a BST in ascending order. The constructor receives the root; next() returns the next smallest value not yet returned, and hasNext() tells whether any value is left. next() is only called when a value remains.

Inputroot = [7,3,15,null,null,9,20]Outputnext() x5: 3,7,9,15,20

Inputthen hasNext()Outputfalse

1 ≤ n ≤ 10⁵ · 0 ≤ Node.val ≤ 10⁶ · ≤ 10⁵ calls · Follow-up: next/hasNext in average O(1) time using O(h) memory.

Try it yourself

Java

class BSTIterator {
    public BSTIterator(TreeNode root) {
        
    }

    public int next() {
        
    }

    public boolean hasNext() {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Don't finish the in-order walk up front — pause it. The explicit stack of the iterative in-order traversal is exactly the iterator's state: its top is always the next smallest node.

PatternBinary Search Tree & In-order

Instinct The tree is a BST? Its in-order walk is a sorted list and every node splits the search space - think "sorted array in tree form", not "visit everything".

Memory hack Left is less, right is more, in-order reads the sorted score - and every node lives inside a (low, high) fence set by its ancestors.

Open the Binary Search Tree & In-order guide →

Approaches

Brute ForceFlatten with In-order into a List

Time O(n) build, O(1) per callSpace O(n)

Do a full in-order traversal in the constructor, which stores all values in sorted order, and keep an index. next() returns vals.get(idx++); hasNext() checks idx < size.

Java

class BSTIterator {
    private final List<Integer> vals = new ArrayList<>();
    private int idx = 0;

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

    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        vals.add(node.val);
        inorder(node.right);
    }

    public int next() {
        return vals.get(idx++);
    }

    public boolean hasNext() {
        return idx < vals.size();
    }
}

Fastest calls, but copies the whole tree and pays O(n) up front even if few calls follow.

OptimalControlled In-order with a Stack

Time O(1) amortized per callSpace O(h)

Push the left spine of the root. next() pops the top (the smallest remaining node) and, if it has a right child, pushes that child's left spine. Every node is pushed and popped exactly once over n calls, so the average cost is O(1); a single call may cost O(h). The stack never holds more than one path.

Java

class BSTIterator {
    private final 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);      // successor lies in the right subtree's left spine
        return node.val;
    }

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

Meets the follow-up: lazy, average O(1) per call, memory bounded by tree height.

Pro tip

Same pattern solves Two Sum IV on a BST in O(h) memory: run one ascending and one descending (push right spine) iterator as two pointers.

At a glance

Level	Approach	Time	Space
Brute Force	Flatten with In-order into a List	`O(n) build, O(1) per call`	`O(n)`
Optimal	Controlled In-order with a Stack	`O(1) amortized per call`	`O(h)`

Common pitfalls

Pushing node.right alone instead of its whole left spine — breaks ordering.
Claiming next() is worst-case O(1); it is O(1) amortized, O(h) worst.
Using a Queue or recursion that runs the whole traversal — no longer lazy.

Interview tips

Start with the list version, then point out the O(n) memory vs the O(h) target.
Prove amortized O(1): each node is pushed once and popped once.
Mention it generalises to merging/iterating several BSTs in sorted order.

Pattern

Paused traversal (explicit stack as iterator state) → lazy, on-demand sorted iteration over a tree.

My notes saved in this browser