BST Iterator Design in DSA Javascript - Execution Trace

Concept Flow - BST Iterator Design

Initialize stack empty

↓

Push left nodes from root

↓

Check stack empty?

Yes→End iteration

No↓

Pop top node

↓

Return node value

↓

Push left nodes of popped node's right child

↓

Repeat from Check stack empty?

The iterator uses a stack to store left nodes. It pops the top node to return its value, then pushes left nodes of the popped node's right child, repeating until stack is empty.

Execution Sample

DSA Javascript

class BSTIterator {
  constructor(root) {
    this.stack = [];
    this._pushLeft(root);
  }
  _pushLeft(node) {
    while (node) {
      this.stack.push(node);
      node = node.left;
    }
  }
  next() {
    const node = this.stack.pop();
    this._pushLeft(node.right);
    return node.val;
  }
  hasNext() {
    return this.stack.length > 0;
  }
}

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

Execution Table

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

💡 Stack becomes empty after popping last node 9, so hasNext() returns false and iteration ends.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	Final
stack	[]	[7,3,1]	[7,3]	[7,4]	[7]	[9,8]	[9]	[]	[]
current node (in next())	null	null	1	3	4	7	8	9	null
returned value	null	null	1	3	4	7	8	9	null

Key Moments - 3 Insights

Why do we push all left nodes from the root initially?

Because the smallest values are on the leftmost path, pushing them first ensures next() returns nodes in ascending order (see execution_table step 1).

What happens when we pop a node with a right child?

We push all left nodes of that right child to the stack to continue in-order traversal (see execution_table step 9 where after popping 7, nodes 9 and 8 are pushed).

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

Because the stack holds nodes yet to be visited; empty stack means traversal is complete (see execution_table step 14).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the top node in the stack after next()?

A Node with value 7

B Node with value 3

C Node with value 4

D Node with value 1

💡 Hint

Check the 'Nodes in Stack' column at step 5 in execution_table

At which step does the stack become empty, ending the iteration?

A Step 14

B Step 9

C Step 13

D Step 1

💡 Hint

Look at the 'Nodes in Stack' column and 'exit_note' in execution_table

If the BST had no right children, how would the stack change after each next() call?

A Stack would grow after each next() call

B Stack would only shrink by popping nodes, no new nodes pushed

C Stack would remain the same size

D Stack would be empty from the start

💡 Hint

Refer to how _pushLeft(node.right) works in execution_table steps where right child is null

Concept Snapshot

BST Iterator uses a stack to traverse nodes in ascending order.
Initialize by pushing all left nodes from root.
next() pops top node, returns its value, then pushes left nodes of popped node's right child.
hasNext() checks if stack is 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 nodes from the root to the stack, so the smallest node is on top. When next() is called, it pops the top node from the stack, returns its value, and then pushes all left nodes of the popped node's right child to the stack. This process continues until the stack is empty, which means all nodes have been visited in ascending order. The hasNext() method simply checks if the stack has any nodes left to visit. This design avoids recursion and allows controlled iteration over the BST.

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 recursion

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 using recursion.

2. Step 2: Identify the main purpose

   It provides a way to get the next smallest element efficiently, which matches To traverse the BST in ascending order without recursion.

3. Final Answer:

   To traverse the BST in ascending order without recursion -> Option A

4. Quick Check:

   BST Iterator = Ascending traversal without recursion [OK]

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

Common Mistakes:

• Confusing iterator with insertion or deletion
• Thinking it balances the tree automatically
• Assuming it uses recursion internally

2. Which of the following is the correct way to initialize a BST Iterator class in JavaScript?

easy

A. function BSTIterator(root) { this.stack = []; this.pushRight(root); }

B. class BSTIterator { constructor(root) { this.stack = []; this.pushLeft(root); } }

C. class BSTIterator { constructor(root) { this.queue = []; this.pushLeft(root); } }

D. function BSTIterator(root) { this.queue = []; this.pushRight(root); }

Solution

1. Step 1: Identify correct class syntax and initialization

   The BST Iterator is usually implemented as a class with a stack to store nodes and a helper method to push left children.

2. Step 2: Check each option

   class BSTIterator { constructor(root) { this.stack = []; this.pushLeft(root); } } correctly uses a class, initializes a stack, and calls pushLeft on root. Others use queue or pushRight which are incorrect for BST Iterator.

3. Final Answer:

   class BSTIterator { constructor(root) { this.stack = []; this.pushLeft(root); } } -> Option B

4. Quick Check:

   Use stack and pushLeft in constructor [OK]

Hint: BST Iterator uses stack and pushLeft method [OK]

Common Mistakes:

• Using queue instead of stack
• Calling pushRight instead of pushLeft
• Using function instead of class syntax

3. Given the BST below and the following code snippet, what will be the output? BST structure: ``` 7 / \ 3 15 / \ 9 20 ``` Code:

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

medium

A. [3, 7, false]

B. [7, 9, true]

C. [3, 7, true]

D. [9, 15, true]

Solution

1. Step 1: Trace the first next() call

   First next() returns the smallest element, which is 3.

2. Step 2: Trace the second next() call

   Second next() returns the next smallest, which is 7.

3. Step 3: Check hasNext()

   After two next() calls, there are still nodes (9, 15, 20), so hasNext() returns true.

4. Final Answer:

   [3, 7, true] -> Option C

5. Quick Check:

   next() returns ascending nodes, hasNext() true if more nodes [OK]

Hint: next() returns next smallest; hasNext() true if stack not empty [OK]

Common Mistakes:

• Assuming next() returns root first
• Confusing hasNext() return value
• Ignoring left subtree nodes

4. Consider this buggy BST Iterator method. What is the main error?

next() {
  const node = this.stack.pop();
  if (node.right) {
    this.pushRight(node.right);
  }
  return node.val;
}

pushRight(node) {
  while (node) {
    this.stack.push(node);
    node = node.right;
  }
}

medium

A. next() should not pop from stack

B. next() should return node.key instead of node.val

C. pushRight should use a queue instead of stack

D. pushRight should push left children, not right

Solution

1. Step 1: Analyze pushRight method

   pushRight pushes right children, but BST Iterator needs to push left children to get next smallest.

2. Step 2: Understand correct pushLeft usage

   Correct method pushes left children of right subtree to stack to maintain ascending order.

3. Final Answer:

   pushRight should push left children, not right -> Option D

4. Quick Check:

   Push left children to stack for correct order [OK]

Hint: Push left children of right subtree, not right children [OK]

Common Mistakes:

• Pushing right children instead of left
• Using queue instead of stack
• Returning wrong node property

5. You want to design a BST Iterator that supports next() and hasNext() in O(1) average time and uses O(h) space, where h is tree height. Which approach best achieves this?

hard

A. Use a stack to store left children and push left nodes of right subtree on next()

B. Store all nodes in an array by inorder traversal at initialization

C. Use recursion to traverse nodes on each next() call

D. Use a queue to store nodes level by level

Solution

1. Step 1: Understand time and space constraints

   O(1) average time per next() and O(h) space means no full traversal storage and no recursion per call.

2. Step 2: Evaluate each approach

   Use a stack to store left children and push left nodes of right subtree on next() uses a stack to store left children and pushes left nodes of right subtree on next(), achieving O(1) average time and O(h) space. Store all nodes in an array by inorder traversal at initialization uses O(n) space. Use recursion to traverse nodes on each next() call uses recursion, not O(1) time. Use a queue to store nodes level by level uses queue level order, not inorder.

3. Final Answer:

   Use a stack to store left children and push left nodes of right subtree on next() -> Option A

4. Quick Check:

   Stack + push left children = O(1) avg time, O(h) space [OK]

Hint: Use stack with left children for efficient BST Iterator [OK]

Common Mistakes:

• Storing all nodes wastes space
• Using recursion causes slow next()
• Using queue gives wrong traversal order