BST Iterator Design in DSA C++ - Execution Trace

Concept Flow - BST Iterator Design

Initialize stack empty

↓

Push all left nodes from root

↓

HasNext?

No→End iteration

Yes↓

Pop top node from stack

↓

Return node value

↓

Push all left nodes from popped node's right child

↩Back to HasNext?

The iterator uses a stack to store nodes. It pushes all left children from the root initially. On next(), it pops the top node, returns its value, then pushes all left children of the popped node's right child.

Execution Sample

DSA C++

class BSTIterator {
  stack<TreeNode*> st;
public:
  BSTIterator(TreeNode* root) { pushLeft(root); }
  int next() { ... }
  bool hasNext() { ... }
private:
  void pushLeft(TreeNode* node) {
    while (node) {
      st.push(node);
      node = node->left;
    }
  }
};

This code initializes the iterator with the root, pushing left nodes. next() returns the next smallest value, hasNext() checks if more nodes remain.

Execution Table

Step	Operation	Nodes in Stack (Top->Bottom)	Pointer Changes	Visual State (Inorder Traversal Progress)
1	Initialize iterator with root=7	[7, 3, 1]	Push 7, then 3, then 1	Stack holds left path from root: 1 <- 3 <- 7
2	hasNext()	Stack: [1, 3, 7]	No change	True, stack not empty
3	next()	Pop 1	Pop 1	Return 1; stack now [3,7]
4	hasNext()	Stack: [3,7]	No change	True
5	next()	Pop 3	Pop 3; push left nodes of 3's right child (4)	Return 3; stack now [4,7]
6	hasNext()	Stack: [4,7]	No change	True
7	next()	Pop 4	Pop 4	Return 4; stack now [7]
8	hasNext()	Stack: [7]	No change	True
9	next()	Pop 7	Pop 7; push left nodes of 7's right child (15, 9)	Return 7; stack now [9,15]
10	hasNext()	Stack: [9,15]	No change	True
11	next()	Pop 9	Pop 9	Return 9; stack now [15]
12	hasNext()	Stack: [15]	No change	True
13	next()	Pop 15	Pop 15; push left nodes of 15's right child (20)	Return 15; stack now [20]
14	hasNext()	Stack: [20]	No change	True
15	next()	Pop 20	Pop 20	Return 20; stack now empty
16	hasNext()	Stack: []	No change	False, iteration ends

💡 Stack empty means no more nodes to visit; 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	After Step 15	Final
stack	[]	[7,3,1]	[7,3]	[7,4]	[7]	[9,15]	[15]	[20]	[]	[]
current_node	root=7	7	1	3	4	7	9	15	20	null
output_values	[]	[]	[1]	[1,3]	[1,3,4]	[1,3,4,7]	[1,3,4,7,9]	[1,3,4,7,9,15]	[1,3,4,7,9,15,20]	[1,3,4,7,9,15,20]

Key Moments - 3 Insights

Why do we push all left nodes from the right child after popping a node?

Because the inorder traversal visits left subtree, then node, then right subtree. After visiting a node, we must visit its right subtree's leftmost nodes next. See execution_table step 5 and 9 where after popping 3 and 7, left nodes of their right children are pushed.

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

The stack always holds the next nodes to visit in inorder order. If it's empty, no nodes remain. This is shown in execution_table steps 2, 4, 6, etc., where hasNext() returns true if stack not empty.

What happens if the BST is empty at initialization?

The stack remains empty because no nodes are pushed. Then hasNext() immediately returns false, ending iteration. This is implied by the exit_note and initial stack state.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What nodes are in the stack after next() is called?

A [4, 7]

B [3, 7]

C [7]

D [1, 3, 7]

💡 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 15

B Step 14

C Step 16

D Step 13

💡 Hint

Look for the step where 'Stack: []' and hasNext() returns false in execution_table.

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

A Stack would become empty immediately

B Stack would only pop nodes without pushing new ones

C Stack would push left nodes after each pop

D Stack would grow larger after each next()

💡 Hint

Refer to variable_tracker stack changes and key_moments about pushing right child's left nodes.

Concept Snapshot

BST Iterator uses a stack to simulate inorder traversal.
Initialize by pushing all left nodes from root.
next() pops top, returns value, then pushes left nodes of popped node's right child.
hasNext() checks if stack is empty.
This gives next smallest element each call.

Full Transcript

The BST Iterator design uses a stack to perform an inorder traversal step-by-step. Initially, it pushes all left children 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 simply checks if the stack is empty to determine if more nodes remain. This approach efficiently returns the next smallest element in the BST without traversing the entire tree at once.