Binary Search Tree Iterator

Implement an iterator over the in-order traversal of a binary search tree. The iterator starts positioned before the smallest value, hasNext() reports whether a next value exists, and next() returns the next-smallest value.

To exercise the iterator here, implement bstIteratorSequence(root): construct the iterator and repeatedly call next() while hasNext() is true, returning the list of emitted values (which is the tree's values in sorted order). The tree is given in level-order, using null for missing children.

The challenge is to do this in O(1) amortized time per next() call and O(height) memory — without flattening the whole tree first.

Hints

· Stuck? Reveal one nudge at a time.

Inorder traversal of a BST returns values in sorted order — but an iterator must pause between them.

Use an explicit stack holding the left spine of the unvisited tree.

next() pops the top and pushes the left spine of its right subtree; hasNext() checks the stack.

Common doubts

A single next() can push a whole left spine, but across the entire traversal every node is pushed and popped exactly once, so the average is O(1).

It uses O(height) memory instead of O(n) — it never holds more than one root-to-node path at a time.

The nodes whose values are next in line but not yet returned, with the smallest on top.

Interview follow-ups

· What an interviewer asks next.

Keep a second stack (or a doubly-threaded structure); the two-stack design mirrors next() with the right spine.

The same stack works — inorder order is defined for any binary tree; it just isn't sorted.

Fun facts

This is the canonical way to make any recursive traversal resumable: replace the call stack with an explicit one.
The same pattern powers merge-style algorithms that walk two BSTs in lockstep.

Asked at

AmazonMicrosoftFacebookGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [7, 3, 15, null, null, 9, 20]
Output: [3, 7, 9, 15, 20]
Draining the iterator yields the values in ascending (inorder) order.

Example 2

Input: root = [2, 1, 3]
Output: [1, 2, 3]
next() returns 1, then 2, then 3; hasNext() is then false.

Constraints

- The number of nodes is in the range [0, 10^5] - 0 <= Node.val <= 10^6 - All Node.val are unique

The obvious iterator precomputes the full inorder list in the constructor and hands out values one at a time — correct, but it costs O(n) memory up front. The interview answer is a controlled recursion: simulate the inorder traversal with an explicit stack, doing only as much work as each next() requires.

Invariant: the stack always holds the path of nodes whose value is next in line but not yet returned. Seed it by pushing the root and every left child (pushLeft) — the top is then the smallest value. Each next() pops the top (the smallest unseen value) and, before returning it, pushes the left spine of that node's right subtree, restoring the invariant. hasNext() is just "is the stack non-empty."

Each node is pushed once and popped once across the whole traversal, so next() is O(1) amortized, and the stack never exceeds the tree height.

Prerequisites

Before you start

· Concepts used directly in the solution.

Inorder = sorted. In a BST, inorder traversal visits values in ascending order.

Iterative inorder. The explicit-stack traversal you can pause and resume.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“What order does next() return values in?”

Ascending — the inorder sequence of the BST.

“What are the memory constraints?”

O(height), not O(n) — don't flatten the whole tree.

The ideal opening — say it like this

I keep a stack holding the left spine of the not-yet-visited part of the tree.

next() pops the top for the smallest value, then pushes the left spine of its right subtree; hasNext() checks the stack.

Understand the problem

Worked example — BST [7, 3, 15, null, null, 9, 20]

seed: push 7,3        stack=[7,3]
next -> 3             push left spine of 3.right (none)  stack=[7]
next -> 7             push left spine of 7.right=15 -> 15,9  stack=[15,9]
next -> 9             stack=[15]
next -> 15            push 20  stack=[20]
next -> 20            stack=[]
result = [3, 7, 9, 15, 20]

Key observations

1Aha

The stack is the paused traversal

It holds the nodes still owed, smallest on top — exactly the inorder frontier.

2Aha

Amortized O(1) per next()

Every node is pushed and popped exactly once over the full iteration.

3Aha

O(height) memory

The stack only ever holds a root-to-node path, never the whole tree.

Brute force vs optimal

	Precompute inorder	Controlled stack
Idea	Flatten to a sorted array in the constructor	Simulate inorder with an explicit stack, lazily
next() time	O(1)	O(1) amortized
Memory	O(n)	O(height)

Both emit the same sorted sequence; the stack version meets the O(height) memory bar. Full code is in the Approaches selector below.

Summary

Key takeaway

Keep a stack of the left spine of the unvisited tree. next() pops the smallest and pushes the left spine of its right subtree; hasNext() checks emptiness. O(1) amortized per call, O(height) memory.

pushLeft(root)
next():   node = stack.pop(); pushLeft(node.right); return node.val
hasNext(): stack not empty