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.