Problem 17.9 · Binary Search TreesMedium

BST Iterator

PatternBST Ordering Combine Structures to Design

What it teaches: Pausing an in-order traversal: keep the stack between calls so each next() is amortised O(1).

Practise it on judges as “Binary Search Tree Iterator”.

The problem

Design BSTIterator(TreeNode root) that returns the BST's values in ascending order: next() returns the next value, hasNext() says whether one remains. Use O(h) memory.

Example 1

Input: BSTIterator([7, 3, 15, null, null, 9, 20]); next, next, hasNext, next
Output: 3, 7, true, 9

Constraints

1 ≤ nodes ≤ 10⁵
next() is only called when hasNext() is true

Pattern clues in the wording

→ "Iterator" over a tree
→ O(h) memory

These clues point to BST Ordering: Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.

Stuck? Take one hint at a time

BSTIterator.java · starter

import java.util.*;

class BSTIterator {
    public BSTIterator(TreeNode root) {}
    public int next() { return 0; }
    public boolean hasNext() { return false; }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["BSTIterator","next","next","hasNext","next","hasNext","next","hasNext","next","hasNext"] args = [[[7,3,15,null,null,9,20]],[],[],[],[],[],[],[],[],[]]	[null,3,7,true,9,true,15,true,20,false]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Controlled in-order stack · O(1) amortised per call

Controlled in-order stack

Time O(1) amortised per call Space O(h)

Constructor pushes the left spine. next() pops a node, pushes the left spine of its right child, returns the value. hasNext() checks the stack.

Approach 1

import java.util.ArrayDeque;
import java.util.Deque;

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

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

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

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

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

Verdict: Each node is pushed and popped exactly once overall.

Before you submit

Edge cases and common mistakes

Test these inputs

Single node
Right-skewed tree

Mistakes people make

Flattening the whole tree in the constructor (O(n) memory).

Interview

Follow-up questions

How do you add a peek() method?

Command Palette

The problem

Approaches

Controlled in-order stack

Edge cases and common mistakes

Follow-up questions

Related problems