Trees crash course ↗ · 175

173. Binary Search Tree Iterator

Stream a BST's values in sorted order, one next() at a time, by pausing an iterative in-order traversal on an explicit stack. The constructor stacks the leftmost spine; each next() pops the smallest unvisited node and stacks the left spine of its right child — amortized O(1) per call.

● MediumBSTStackDesignTypeScript

PROBLEM What we're solving

Build an iterator over a BST that yields values in sorted (in-order) order, exposing next() (return the next-smallest value) and hasNext() (is there another value?). Both must be average O(1) time and O(h) space — you cannot pre-flatten the whole tree into a sorted array (that would be O(n) space).

Worked example — tree [7,3,15,null,null,9,20] (root 7, left 3, right 15 whose children are 9 and 20):

next() → 3
next() → 7
hasNext() → true
next() → 9
hasNext() → true
next() → 15
hasNext() → true
next() → 20
hasNext() → false

KEY IDEA Pause the iterative in-order traversal between calls

Insight → the classic iterative in-order walk uses an explicit stack and runs to completion. A BST iterator is that exact loop, frozen between steps. Keep the stack as a member; its invariant is "every node whose value is the next-smallest, plus its waiting ancestors, are on the stack with the smallest on top." The constructor stacks the leftmost spine. Each next() pops the top (the smallest unvisited node), then stacks the left spine of its right child so the new smallest sits on top again — leaving the invariant intact for the following call.

RECIPE pushLeft, then pop-and-pushLeft-right

0 · The helper. pushLeft(node) pushes node and every left descendant, so the smallest of that subtree lands on top. This is the one move both the constructor and next() reuse.
1 · Constructor. Call pushLeft(root). The stack now holds the path from the root down to the minimum node, with the minimum on top.
2 · next().Pop the top node — it's the next-smallest. Before returning its value, call pushLeft(node.right): the popped node's left subtree is finished, so the only smaller-than-everything-else candidates now live in its right subtree's left spine.
3 · hasNext(). Return stack.length > 0. A non-empty stack means there is still a node waiting to be popped.

Classic confusion → the per-call cost looks like O(h) because next() can push a whole spine. But each node is pushed once and popped once across the entireiteration, so the total work over n calls is O(n) — that's amortized O(1) per next(), not O(h). The stack itself never exceeds the tree's height h, giving O(h) space.

COST Complexity & alternatives

Pre-flatten to sorted array

O(n) space

O(1) next, but stores all n values and does O(n) upfront work.

Paused stack traversal

O(h) space

Amortized O(1) next/hasNext; stack ≤ tree height.

Why amortized O(1)

A single next() may push up to h nodes (a long left spine) or zero. But summed over a full traversal, every node is pushed and popped exactly once, so n calls cost O(n) total — O(1) each on average. Space is O(h): the stack only ever holds nodes along one root-to-node path — O(log n) balanced, O(n) degenerate.

Pattern transfer → this paused-stack idea generalizes: a k-merge over BSTs can interleave several BSTIterators, Kth Smallest in a BST is just k calls to next(), and the same "freeze the traversal in a member structure" trick powers Flatten Nested List Iterator and Peeking Iterator.

RUN IT Replay next()/hasNext() over a stack-backed in-order iterator

BST (level-order) =calls =

step 0 / 21

STARTConstructor. Seed the stack by pushing the entire left spine from the root. The smallest value ends up on top, ready for the first next().

1class BSTIterator {
2  private stack: TreeNode[] = [];
3 
4▶  constructor(root: TreeNode | null) {
5▶    this.pushLeft(root);          // seed: leftmost spine
6▶  }
7 
8  private pushLeft(node: TreeNode | null): void {
9    while (node !== null) {
10      this.stack.push(node);      // remember ancestors
11      node = node.left;           // dive to the smallest
12    }
13  }
14 
15  next(): number {
16    const node = this.stack.pop()!;   // smallest unvisited
17    this.pushLeft(node.right);        // open up its right spine
18    return node.val;
19  }
20 
21  hasNext(): boolean {
22    return this.stack.length > 0;     // anything left to pop?
23  }
24}

State

cur (pushLeft)

[]

stack

∅

stack top

false

hasNext()

—

last return

cur in pushLeftstack contents / topjust emitted / truehasNext false

slowfast

TYPESCRIPT The solution, annotated

bstIterator.ts
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

class BSTIterator {
  private stack: TreeNode[] = [];

  constructor(root: TreeNode | null) {
    this.pushLeft(root);              // seed with the leftmost spine
  }

  // Push a node and every left descendant; the smallest ends up on top.
  private pushLeft(node: TreeNode | null): void {
    while (node !== null) {
      this.stack.push(node);
      node = node.left;
    }
  }

  next(): number {
    const node = this.stack.pop()!;   // next-smallest unvisited node
    this.pushLeft(node.right);        // its left subtree is done; open the right
    return node.val;
  }

  hasNext(): boolean {
    return this.stack.length > 0;     // unvisited nodes remain iff stack non-empty
  }
}

Reading it block by block

The member stack. stackpersists between calls and holds the ancestors-still-owed-a-visit, with the next value to return on top. This single field is the whole "paused traversal" state.

Constructor → pushLeft(root). Seed the stack with the leftmost spine. After this, the minimum node of the tree is on top, so the first next() is ready.

pushLeft(node). Walk down left children, pushing each. The smallest value in node's subtree ends up on top. Called with rootat construction and with each popped node's right child during next().

next() — pop then open right. stack.pop() is the next-smallest node. Its left subtree is already exhausted, so call pushLeft(node.right) to stack the left spine of its right subtree (the new candidates), then return node.val.

hasNext(). The stack is non-empty exactly when a node is still waiting to be popped, so stack.length > 0 answers it in O(1).

Complexity → hasNext() is O(1). next() is amortized O(1): a single call can push up to h nodes, but each node is pushed and popped once over the full traversal, so n calls total O(n). Space is O(h) — the stack holds at most one root-to-node path (O(log n) balanced, O(n) degenerate).

INTERVIEWFollow-ups they'll ask

"Prove next() is average O(1)." Amortized analysis: across an entire iteration every node is pushed exactly once and popped exactly once, so total work for n next() calls is O(n) → O(1) each on average.
"Why not flatten the tree into a sorted array up front?" That uses O(n) space; the stack approach uses only O(h). It also wastes work if the caller stops early after a few next() calls.
"Add a prev() / bidirectional iterator?"Harder — you'd keep a second stack for the reverse spine, or maintain parent pointers, since a single in-order stack only moves forward.
"Merge two BSTs into one sorted stream?" Run two BSTIterators and repeatedly take next() from whichever has the smaller current head — like merging two sorted lists.

OPTIMAL BST

bstIterator.ts
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

class BSTIterator {
  private stack: TreeNode[] = [];

  constructor(root: TreeNode | null) {
    this.pushLeft(root);              // seed with the leftmost spine
  }

  // Push a node and every left descendant; the smallest ends up on top.
  private pushLeft(node: TreeNode | null): void {
    while (node !== null) {
      this.stack.push(node);
      node = node.left;
    }
  }

  next(): number {
    const node = this.stack.pop()!;   // next-smallest unvisited node
    this.pushLeft(node.right);        // its left subtree is done; open the right
    return node.val;
  }

  hasNext(): boolean {
    return this.stack.length > 0;     // unvisited nodes remain iff stack non-empty
  }
}

ALT 1 Pre-flatten — full in-order into an array, then index

O(n) construction · O(1) next/hasNext · O(n) space

Do the whole in-order traversal up front into a sorted array and keep an index pointer. Dead simple, and each next() is a true O(1) array read — but it stores all n values regardless of how few the caller consumes.

approach-2.ts
class BSTIterator {
  private values: number[] = [];
  private i = 0;

  constructor(root: TreeNode | null) {
    const inorder = (node: TreeNode | null): void => {
      if (node === null) return;
      inorder(node.left);
      this.values.push(node.val);
      inorder(node.right);
    };
    inorder(root);
  }

  next(): number {
    return this.values[this.i++];
  }

  hasNext(): boolean {
    return this.i < this.values.length;
  }
}

Note → Correct and the operations are genuinely O(1), but it uses O(n) space and pays the full traversal cost in the constructor even if the caller only ever calls next() a few times. The stack version trims this to O(h) space with amortized O(1) calls.

MNEMONIC The one-liner

"Constructor stacks the left spine; next() pops, then stacks the right child’s left spine."

TRIGGERS When you see _ → reach for _

"iterator over a BST in sorted order"	paused iterative in-order + stack
next() / hasNext() with O(h) memory	member stack of waiting ancestors
pop the smallest, then go right	pushLeft(node.right) after each pop
"stream sorted values one at a time"	freeze the traversal between calls

SKELETON The reusable shape

skeleton.ts
class BSTIterator {
  private stack: TreeNode[] = [];
  constructor(root: TreeNode | null) { this.pushLeft(root); }
  private pushLeft(node: TreeNode | null): void {
    while (node) { this.stack.push(node); node = node.left; }
  }
  next(): number {
    const node = this.stack.pop()!;
    this.pushLeft(node.right);
    return node.val;
  }
  hasNext(): boolean { return this.stack.length > 0; }
}

FLASHCARDS Tap to flip

What state does a BSTIterator keep between calls?

A single member stack holding the path of waiting ancestors, with the next-smallest node on top — the frozen state of an iterative in-order traversal.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What does the BSTIterator constructor do?

QUESTION 02

Inside next(), after popping a node, which subtree gets pushed onto the stack?

QUESTION 03

For tree [7,3,15,null,null,9,20], what are the first two values returned by next()?

QUESTION 04

What is the amortized time complexity of next()?

QUESTION 05

What is the space complexity, and why?

QUESTION 06

How does hasNext() determine whether more values remain?

QUESTION 07

Why is the paused-stack iterator preferred over pre-flattening the BST into a sorted array?

QUESTION 08

#173 · Binary Search Tree IteratorStream a BST in sorted order with next()/hasNext() by simulating in-order traversal on an explicit stack: seed the leftmost spine, and after each pop push the left spine of the right child. Amortized O(1) per call, O(h) space.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Pause the iterative in-order traversal between calls

RECIPE pushLeft, then pop-and-pushLeft-right

COST Complexity & alternatives

Why amortized O(1)

RUN IT Replay next()/hasNext() over a stack-backed in-order iterator

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL BST

ALT 1 Pre-flatten — full in-order into an array, then index

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _