#173 Binary Search Tree Iterator

frequently reported atMeta LinkedIn Microsoft Amazon Google Apple

the problem

In plain words

Implement BSTIterator over a BST's inorder sequence: next() returns the next smallest value, hasNext() tells whether one exists.

in [7,3,15,null,null,9,20]; next, next, hasNext, next, hasNext, next, hasNext, next, hasNext

out 3, 7, true, 9, true, 15, true, 20, false

1 ≤ number of nodes ≤ 10⁵
0 ≤ Node.val ≤ 10⁶
At most 10⁵ calls
Follow-up: average O(1) time and O(h) memory

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBST property Iterative tree DFS (explicit stack)

Pause the iterative inorder between pops. The stack is the iterator's state: it holds exactly the nodes still waiting to be visited on the current left spine.

solutions

From brute force to optimal

Do the whole inorder in the constructor; next() reads the list.

Constructor: inorder into an ArrayList.
next(): return list.get(i++).
hasNext(): i < size.

timeO(n) build, O(1) per call

All work happens up front.

spaceO(n)

Stores every value — misses the O(h) follow-up.

javaclass BSTIterator (flatten)java.util.*

1class BSTIterator {2    private final List<Integer> sorted = new ArrayList<>();3    private int next = 0;4 5    public BSTIterator(TreeNode root) {6        collect(root);                 // pay O(n) time and memory up front7    }8 9    private void collect(TreeNode node) {10        if (node == null) return;11        collect(node.left);12        sorted.add(node.val);13        collect(node.right);14    }15 16    public int next() {17        return sorted.get(next++);18    }19 20    public boolean hasNext() {21        return next < sorted.size();22    }23}

Keep the left spine on a stack; next() pops one node and pushes the left spine of its right child.

Constructor: push root and all its left descendants.
next(): pop, push the left spine of node.right, return node.val.
hasNext(): stack not empty.

timeO(1) amortized

Each node is pushed and popped exactly once over the whole iteration: n pushes / n calls.

spaceO(h)

The stack never holds more than one root-to-leaf spine.

javaclass BSTIterator (stack)java.util.*

1class BSTIterator {2    private final Deque<TreeNode> stack = new ArrayDeque<>();   // the left spine still to visit3 4    public BSTIterator(TreeNode root) {5        pushLeft(root);6    }7 8    private void pushLeft(TreeNode node) {9        for (; node != null; node = node.left) stack.push(node);10    }11 12    public int next() {13        TreeNode node = stack.pop();      // smallest value not yet returned14        pushLeft(node.right);             // its successor lives in the right subtree's left spine15        return node.val;16    }17 18    public boolean hasNext() {19        return !stack.isEmpty();20    }21}

sim

Dry run

loading simulation…

javajava.util.*

1class BSTIterator {2    private final Deque<TreeNode> stack = new ArrayDeque<>();   // the left spine still to visit3 4    public BSTIterator(TreeNode root) {5        pushLeft(root);6    }7 8    private void pushLeft(TreeNode node) {9        for (; node != null; node = node.left) stack.push(node);10    }11 12    public int next() {13        TreeNode node = stack.pop();      // smallest value not yet returned14        pushLeft(node.right);             // its successor lives in the right subtree's left spine15        return node.val;16    }17 18    public boolean hasNext() {19        return !stack.isEmpty();20    }21}

in the room

How to say it in the interview

talk track

Explain the amortized argument: a single next() can push h nodes, but over n calls there are only n pushes.

traps

Flattening the whole tree in the constructor — it works, but uses O(n) memory instead of O(h).
Forgetting to push the left spine of node.right after a pop, so values are skipped.
Moving the iterator inside hasNext() — it must only check !stack.isEmpty().

what they ask next

Follow-ups

Two Sum IV - Input is a BST (LC 653)?

Run one ascending iterator and one descending iterator (mirror: right spine) as two pointers: O(n) time, O(h) space.

before you submit

Edge cases to test

One node: hasNext is true, next returns it, then hasNext is false.
hasNext called several times in a row must not move the iterator.
A left-skewed tree → the constructor pushes all n nodes; later calls push nothing.

practise next