BST Iterator Design in DSA Go - 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

↩Back to Check if stack empty?

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 Go

func (it *BSTIterator) Next() int {
    node := it.stack[len(it.stack)-1]
    it.stack = it.stack[:len(it.stack)-1]
    val := node.Val
    it.pushLeft(node.Right)
    return val
}

This code returns the next smallest value in the BST by popping the top node from the stack and pushing all left children of its right subtree.

Execution Table

Step	Operation	Nodes in Stack (Top to Bottom)	Pointer Changes	Visual State
1	Initialize iterator with root=7	[7]	Push 7	Stack: [7]
2	Push all left nodes from 7	[3, 7]	Push 3	Stack: [3, 7]
3	Push all left nodes from 3	[1, 3, 7]	Push 1	Stack: [1, 3, 7]
4	Call Next()	Pop 1	Pop 1	Stack: [3, 7] → Output: 1
5	Push left nodes from 1's right (nil)	[3, 7]	No push	Stack: [3, 7]
6	Call Next()	Pop 3	Pop 3	Stack: [7] → Output: 3
7	Push left nodes from 3's right (5)	[5, 7]	Push 5	Stack: [5, 7]
8	Push left nodes from 5	[5, 7]	No left child	Stack: [5, 7]
9	Call Next()	Pop 5	Pop 5	Stack: [7] → Output: 5
10	Push left nodes from 5's right (nil)	[7]	No push	Stack: [7]
11	Call Next()	Pop 7	Pop 7	Stack: [] → Output: 7
12	Push left nodes from 7's right (15)	[15]	Push 15	Stack: [15]
13	Push left nodes from 15	[13, 15]	Push 13	Stack: [13, 15]
14	Call Next()	Pop 13	Pop 13	Stack: [15] → Output: 13
15	Push left nodes from 13's right (nil)	[15]	No push	Stack: [15]
16	Call Next()	Pop 15	Pop 15	Stack: [] → Output: 15
17	Check if stack empty	[]	No nodes	Stack empty → No next element

💡 Stack is empty, no more elements to iterate

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 11	After Step 13	Final
stack	[]	[1, 3, 7]	[5, 7]	[7]	[]	[13, 15]	[]
current_node	7	3	5	7	15	13	15
output_values	[]	[1]	[1,3]	[1,3,5]	[1,3,5,7]	[1,3,5,7,13]	[1,3,5,7,13,15]

Key Moments - 3 Insights

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

Because the smallest element in a BST is the leftmost node. Pushing all left nodes ensures the top of the stack is always the next smallest element (see execution_table rows 1-3).

Why do we push left nodes from the popped node's right child after Next()?

Because after visiting a node, the next smallest elements are in its right subtree. We push all left children of that right subtree to maintain the correct order (see execution_table rows 6-7 and 12-13).

What happens when the stack becomes empty?

It means we have visited all nodes in ascending order. The iterator has no more elements to return (see execution_table row 17).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4. What is the top node in the stack after popping?

A 3

B 7

C 1

D 5

💡 Hint

Check the 'Nodes in Stack' column at Step 4 after popping 1

At which step does the iterator push the node with value 13 onto the stack?

A Step 7

B Step 13

C Step 12

D Step 9

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns around Steps 12 and 13

If the BST had no right children, how would the stack change after calling Next()?

A It would push left nodes from the right child

B It would remain unchanged after popping

C It would become empty after popping

D It would push the root node again

💡 Hint

Refer to the 'Push left nodes from popped node's right child' action in execution_table rows 5 and 10

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 all left nodes from popped node's right child.
HasNext() checks if stack is empty.
This simulates in-order traversal lazily.

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 from the root onto the stack, so the smallest element is on top. Each call to Next() pops the top node, returns its value, and then pushes all left children of the popped node's right subtree. This ensures the next smallest element is always on top of the stack. When the stack is empty, there are no more elements to iterate. This approach efficiently returns elements in ascending order without traversing the entire tree at once.