BST Iterator Design in DSA Typescript - Execution Trace

Concept Flow - BST Iterator Design

Initialize stack empty

↓

Push all left nodes from root

↓

Check if stack empty?

Yes→No next element

No↓

Pop top node from stack

↓

Return popped node's value

↓

Push all left nodes from popped node's right child

↓

Repeat check for next element

The iterator uses a stack to store nodes. It pushes all left children first, then pops nodes to return values, pushing left children of right subtrees as it goes.

Execution Sample

DSA Typescript

class BSTIterator {
  stack: TreeNode[] = [];
  constructor(root: TreeNode) {
    this.pushLeft(root);
  }
  pushLeft(node: TreeNode | null) {
    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;
  }
}

This code creates an iterator over a BST that returns nodes in ascending order using a stack to track left nodes.

Execution Table

Step	Operation	Stack Nodes (top to bottom)	Pointer Changes	Visual State
1	Initialize iterator with root=7	[1, 3, 7]	Push 7, then 3, then 1	Stack: 1(top) -> 3 -> 7 -> null
2	Call hasNext()	Stack unchanged	No pointer change	Stack: 1(top) -> 3 -> 7 -> null
3	Call next()	Pop 1	Pop 1; push left nodes of 1.right (null)	Returned 1; Stack: 3(top) -> 7 -> null
4	Call hasNext()	Stack unchanged	No pointer change	Stack: 3(top) -> 7 -> null
5	Call next()	Pop 3	Pop 3; push left nodes of 3.right (5)	Returned 3; Stack: 5(top) -> 7 -> null
6	Call hasNext()	Stack unchanged	No pointer change	Stack: 5(top) -> 7 -> null
7	Call next()	Pop 5	Pop 5; push left nodes of 5.right (null)	Returned 5; Stack: 7(top) -> null
8	Call hasNext()	Stack unchanged	No pointer change	Stack: 7(top) -> null
9	Call next()	Pop 7	Pop 7; push left nodes of 7.right (9)	Returned 7; Stack: 9(top) -> null
10	Call hasNext()	Stack unchanged	No pointer change	Stack: 9(top) -> null
11	Call next()	Pop 9	Pop 9; push left nodes of 9.right (null)	Returned 9; Stack: empty
12	Call hasNext()	Stack empty	No pointer change	Stack: empty
13	Call next()	No nodes to pop	No pointer change	No next element, iteration ends

💡 Stack becomes empty after all nodes are visited; hasNext() returns false and next() cannot proceed.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	Final
stack	[]	[7,3,1]	[7,3]	[7,5]	[7]	[9]	[]	[]
current node popped	null	null	1	3	5	7	9	null
returned value	null	null	1	3	5	7	9	null

Key Moments - 3 Insights

Why do we push all left children onto the stack at initialization and after popping a node?

Because the smallest values are always in the left subtree, pushing all left children ensures the next smallest node is on top of the stack, as shown in steps 1 and 9 in the execution_table.

What happens if the popped node has no right child?

No new nodes are pushed onto the stack after popping, so the stack size decreases, as seen in steps 3 and 7 where no nodes are pushed after popping nodes 1 and 5.

Why does hasNext() check if the stack is empty?

Because the stack holds all nodes yet to be visited; if empty, no next node exists. This is clear in step 12 where the stack is empty and hasNext() returns false.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the top node on the stack after the next() call?

A Node with value 5

B Node with value 3

C Node with value 7

D Stack is empty

💡 Hint

Refer to the 'Stack Nodes' column at step 5 in the execution_table.

At which step does the stack become empty, indicating no more elements to iterate?

A Step 11

B Step 12

C Step 13

D Step 10

💡 Hint

Check the 'Stack Nodes' column and 'exit_note' in the execution_table.

If the BST had an additional left child under node 1, how would the stack change after initialization (step 1)?

A Stack would include the new left child on top

B Stack would remain the same

C Stack would only have the root node

D Stack would be empty

💡 Hint

Refer to the 'pushLeft' operation in the code and how left children are pushed onto the stack.

Concept Snapshot

BST Iterator uses a stack to traverse nodes in ascending order.
Initialize by pushing all left children from root.
next() pops top node, pushes left children of its right subtree.
hasNext() checks if stack is not empty.
This simulates in-order traversal without recursion.

Full Transcript

The BST Iterator design uses a stack to simulate in-order traversal of a binary search tree. Initially, it pushes all left children starting from the root onto the stack. Each call to next() pops the top node from the stack, returns its value, and then pushes all left children of the popped node's right child. The hasNext() method returns true if the stack is not empty, indicating more nodes to visit. This approach allows iteration over the BST in ascending order without recursion, maintaining the current traversal state in the stack.

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