BST Iterator Design in DSA Typescript

Mental Model

A BST iterator lets you see the tree's values one by one in order, like reading a book page by page without holding the whole book open.

Analogy: Imagine a bookmark that remembers where you stopped reading in a sorted book, so you can pick up exactly where you left off without rereading pages.

      7
     / \
    3   15
       /  \
      9    20

Stack: []
Iterator at start, ready to go leftmost.

Dry Run Walkthrough

Input: BST with nodes 7, 3, 15, 9, 20; iterate through all values in ascending order

Goal: Return values one by one in sorted order using next() and hasNext() methods

Step 1: Initialize iterator by pushing leftmost nodes onto stack

Stack: [7, 3]
Current node not yet returned

Why: We start at the smallest value by going left as far as possible

Step 2: Call next(), pop 3 from stack and return it

Stack: [7]
Returned value: 3

Why: 3 is the smallest node, so we return it first

Step 3: Call next(), pop 7 from stack and return it; push leftmost nodes of 7's right child (15)

Stack: [15, 9]
Returned value: 7

Why: After 7, we explore its right subtree starting at 15

Step 4: Call next(), pop 9 from stack and return it

Stack: [15]
Returned value: 9

Why: 9 is next smallest after 7

Step 5: Call next(), pop 15 from stack and return it; push leftmost nodes of 15's right child (20)

Stack: [20]
Returned value: 15

Why: After 15, move to its right child 20

Step 6: Call next(), pop 20 from stack and return it

Stack: []
Returned value: 20

Why: 20 is the largest node, iteration ends after this

Step 7: Call hasNext(), return false since stack is empty

Stack: []
No more nodes to return

Why: No nodes left means iteration is complete

Result:

Stack: []
Returned values in order: 3 -> 7 -> 9 -> 15 -> 20
Iteration complete

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

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

  constructor(root: TreeNode | null) {
    this.pushLeft(root);
  }

  private pushLeft(node: TreeNode | null): void {
    while (node !== null) {
      this.stack.push(node); // push current node to stack
      node = node.left; // move to left child
    }
  }

  next(): number {
    const node = this.stack.pop()!; // pop top node
    if (node.right !== null) {
      this.pushLeft(node.right); // push left path of right subtree
    }
    return node.val; // return current node's value
  }

  hasNext(): boolean {
    return this.stack.length > 0; // check if any nodes left
  }
}

// Driver code to test iterator
const root = new TreeNode(7,
  new TreeNode(3),
  new TreeNode(15, new TreeNode(9), new TreeNode(20))
);
const iterator = new BSTIterator(root);
const result: number[] = [];
while (iterator.hasNext()) {
  result.push(iterator.next());
}
console.log(result.join(' -> ') + ' -> null');

while (node !== null) { this.stack.push(node); // push current node to stack node = node.left; // move to left child }

push all left children to stack to reach smallest node

const node = this.stack.pop()!; // pop top node

pop the next smallest node to return

if (node.right !== null) { this.pushLeft(node.right); // push left path of right subtree }

after returning a node, prepare stack with left path of its right subtree

return node.val; // return current node's value

return the value of the current node

return this.stack.length > 0; // check if any nodes left

check if iteration can continue

Output

3 -> 7 -> 9 -> 15 -> 20 -> null

Complexity Analysis

Time: O(1) amortized per next() call because each node is pushed and popped once

Space: O(h) where h is tree height, due to stack storing left path nodes

vs Alternative: Compared to inorder traversal storing all nodes (O(n) space), this uses less memory by storing only path nodes

Edge Cases

Empty tree (root is null)

Iterator stack remains empty, hasNext() returns false immediately

DSA Typescript

while (node !== null) { this.stack.push(node); node = node.left; }

Tree with single node

Stack contains one node, next() returns that node's value, then hasNext() returns false

DSA Typescript

const node = this.stack.pop()!;

Tree with only left children

Stack initially contains all nodes, next() returns nodes in ascending order without pushing right children

DSA Typescript

while (node !== null) { this.stack.push(node); node = node.left; }

When to Use This Pattern

When asked to iterate over a BST in sorted order with next() and hasNext(), use a controlled stack to simulate inorder traversal lazily.

Common Mistakes

Mistake: Pushing all nodes of the tree onto stack at once, using O(n) space
Fix: Only push leftmost path nodes and push right subtree's left path when needed

Mistake: Not pushing left children of right subtree after popping a node
Fix: After popping a node, call pushLeft on its right child to maintain correct order

Summary

Provides an iterator to traverse BST nodes in ascending order using controlled stack.

Use when you want to access BST elements one by one without storing all nodes.

The key is to push leftmost nodes and update stack with right subtree's left path after each next().

Practice

1. What is the main purpose of a BST Iterator in a binary search tree?

easy

A. To traverse the BST in ascending order without storing all elements at once

B. To insert new nodes into the BST

C. To delete nodes from the BST

D. To balance the BST automatically

Solution

1. Step 1: Understand BST Iterator functionality

   A BST Iterator is designed to traverse the tree in sorted order, typically ascending, without loading all nodes into memory at once.

2. Step 2: Compare options with BST Iterator purpose

   Options B, C, and D relate to modifying the tree, not iterating over it. To traverse the BST in ascending order without storing all elements at once correctly describes the iterator's purpose.

3. Final Answer:

   To traverse the BST in ascending order without storing all elements at once -> Option A

4. Quick Check:

   BST Iterator = In-order traversal on demand [OK]

Hint: BST Iterator returns next smallest element step-by-step [OK]

Common Mistakes:

• Confusing iterator with insertion or deletion operations
• Thinking iterator balances the tree
• Assuming iterator stores all nodes at once

2. Which of the following is the correct TypeScript method signature for the next() method in a BST Iterator class that returns the next smallest number?

easy

A. next(value: number): number

B. next(): void

C. next(): number

D. next(): boolean

Solution

1. Step 1: Understand the purpose of next()

   The next() method should return the next smallest number in the BST, so it must return a number.

2. Step 2: Analyze method signatures

   next(): number returns a number with no parameters, which fits the iterator pattern. next(): void returns void, so no value is returned. next(value: number): number takes a parameter, which is not needed. next(): boolean returns boolean, which is incorrect.

3. Final Answer:

   next(): number -> Option C

4. Quick Check:

   next() returns next smallest number [OK]

Hint: next() returns a number without parameters [OK]

Common Mistakes:

• Adding unnecessary parameters to next()
• Returning void instead of number
• Returning boolean instead of number

3. Given the following BST Iterator usage in TypeScript, what will be the output printed?

const root = {
  val: 7,
  left: { val: 3, left: null, right: null },
  right: { val: 15, left: { val: 9, left: null, right: null }, right: { val: 20, left: null, right: null } }
};

const iterator = new BSTIterator(root);
console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.hasNext());
console.log(iterator.next());

medium

A. [3, 7, true, 9]

B. [7, 3, true, 9]

C. [3, 7, false, 9]

D. [3, 9, true, 15]

Solution

1. Step 1: Understand BST in-order traversal order

   The BST nodes in ascending order are 3, 7, 9, 15, 20.

2. Step 2: Trace iterator calls

   First next() returns 3, second next() returns 7, hasNext() returns true because more nodes exist, third next() returns 9.

3. Final Answer:

   [3, 7, true, 9] -> Option A

4. Quick Check:

   In-order traversal = 3,7,9,... [OK]

Hint: Remember BST in-order is sorted ascending [OK]

Common Mistakes:

• Mixing up left and right subtree order
• Assuming hasNext() returns next value
• Confusing node values order

4. Consider this partial TypeScript BST Iterator class code. What is the bug?

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

  constructor(root: TreeNode | null) {
    this.pushLeft(root);
  }

  pushLeft(node: TreeNode | null) {
    while (node !== null) {
      this.stack.push(node);
      node = node.right;  // Bug here
    }
  }

  next(): number {
    const node = this.stack.pop()!;
    this.pushLeft(node.right);
    return node.val;
  }

  hasNext(): boolean {
    return this.stack.length > 0;
  }
}

medium

A. next() should pop from the front, not the end

B. In pushLeft, should traverse left child, not right

C. hasNext() should check if stack is empty incorrectly

D. Constructor should not call pushLeft

Solution

1. Step 1: Analyze pushLeft method

   pushLeft should push all left children to stack to simulate in-order traversal. The code incorrectly moves to node.right instead of node.left.

2. Step 2: Check other methods

   next() correctly pops from stack and pushes left children of right subtree. hasNext() correctly checks stack length. Constructor correctly calls pushLeft.

3. Final Answer:

   In pushLeft, should traverse left child, not right -> Option B

4. Quick Check:

   pushLeft must go left to simulate in-order [OK]

Hint: pushLeft must follow left children, not right [OK]

Common Mistakes:

• Traversing right child in pushLeft instead of left
• Misunderstanding stack usage in iterator
• Incorrect pop direction in next()

5. You want to design a BST Iterator that supports peek() to see the next smallest element without advancing the iterator. Which approach best supports this feature efficiently?

hard

A. Use a queue to store nodes in BFS order

B. Store all BST elements in an array and use an index pointer

C. Traverse the BST every time peek() is called

D. Use a stack to store left children and keep the top as peek value

Solution

1. Step 1: Understand peek() requirement

   peek() must return next smallest element without moving forward, so the next element must be accessible without popping.

2. Step 2: Evaluate approaches

   Use a stack to store left children and keep the top as peek value uses a stack with left children; the top of the stack is the next smallest element, so peek() can return it efficiently. Store all BST elements in an array and use an index pointer stores all elements but uses extra memory. Traverse the BST every time peek() is called is inefficient as it traverses repeatedly. Use a queue to store nodes in BFS order uses BFS order, which is not sorted.

3. Final Answer:

   Use a stack to store left children and keep the top as peek value -> Option D

4. Quick Check:

   Stack top = next smallest for peek() [OK]

Hint: Stack top always holds next smallest for peek() [OK]

Common Mistakes:

• Using BFS queue which is unordered
• Re-traversing tree on every peek() call
• Storing all elements wastes memory