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

Yes↓

Pop top node

↓

Return popped 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 first, then pops nodes to return values, pushing left children of right subtrees as it goes.

Execution Sample

DSA C#

class BSTIterator {
  Stack<TreeNode> stack = new Stack<TreeNode>();
  public BSTIterator(TreeNode root) {
    PushLeft(root);
  }
  void PushLeft(TreeNode node) {
    while(node != null) { stack.Push(node); node = node.left; }
  }
  public int Next() {
    var node = stack.Pop();
    PushLeft(node.right);
    return node.val;
  }
  public bool HasNext() {
    return stack.Count > 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 (BST nodes visited)
1	Initialize stack empty	[]	stack = []	No nodes visited
2	PushLeft(root=7)	[7, 3, 1]	Push 7, then 3, then 1	No nodes visited
3	HasNext()	[7, 3, 1]	Check stack.Count > 0	No nodes visited
4	Next()	[7, 3]	Pop 1 from stack	Visit node 1
5	PushLeft(1.right=null)	[7, 3]	No push, right child null	Visited 1
6	HasNext()	[7, 3]	Check stack.Count > 0	Visited 1
7	Next()	[7]	Pop 3 from stack	Visit node 3
8	PushLeft(3.right=5)	[7, 5]	Push 5	Visited 1,3
9	HasNext()	[7, 5]	Check stack.Count > 0	Visited 1,3
10	Next()	[7]	Pop 5 from stack	Visit node 5
11	PushLeft(5.right=null)	[7]	No push, right child null	Visited 1,3,5
12	HasNext()	[7]	Check stack.Count > 0	Visited 1,3,5
13	Next()	[]	Pop 7 from stack	Visit node 7
14	PushLeft(7.right=9)	[9]	Push 9	Visited 1,3,5,7
15	HasNext()	[9]	Check stack.Count > 0	Visited 1,3,5,7
16	Next()	[]	Pop 9 from stack	Visit node 9
17	PushLeft(9.right=null)	[]	No push, right child null	Visited 1,3,5,7,9
18	HasNext()	[]	Check stack.Count > 0	All nodes visited, stack empty

💡 Stack empty means all nodes visited, iteration ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 10	After Step 13	After Step 16	Final
stack	[]	[7, 3, 1]	[7, 3]	[7]	[7]	[]	[]	[]
visited_nodes	[]	[]	[1]	[1,3]	[1,3,5]	[1,3,5,7]	[1,3,5,7,9]	[1,3,5,7,9]

Key Moments - 3 Insights

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

Because the smallest nodes are always on the left, pushing all left children ensures the next smallest node is on top of the stack (see steps 2, 8, 14).

What happens if the right child of a popped node is null?

No nodes are pushed to the stack in that case, so the stack size decreases (see steps 5, 11, 17).

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

Because the stack holds nodes yet to be visited; empty stack means all nodes visited (see steps 3, 6, 9, 12, 15, 18).

Visual Quiz - 3 Questions

Look at the execution table at step 4. What node value is popped from the stack?

A 5

B 3

C 1

D 7

💡 Hint

Check the 'Operation' and 'Nodes in Stack' columns at step 4.

At which step does the stack become empty, indicating all nodes are visited?

A Step 16

B Step 18

C Step 17

D Step 19

💡 Hint

Look at the 'Nodes in Stack' column and find when it shows [].

If the node with value 3 had no right child, how would the stack change after popping it?

A It would not push any new nodes, stack size decreases

B It would push node 5 onto the stack

C It would push node 7 onto the stack

D Stack would become empty immediately

💡 Hint

Refer to steps 7 and 8 where right child pushes happen.

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 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, all left children from the root are pushed onto the stack. When Next() is called, the top node is popped and its value returned. Then, all left children of the popped node's right child are pushed onto the stack. HasNext() returns true if the stack is not empty, meaning there are more nodes to visit. This approach ensures nodes are returned in ascending order without recursion. The execution table shows step-by-step stack changes and visited nodes, clarifying how the iterator moves through the tree.

Practice

1. What is the main purpose of a BST Iterator in data structures?

easy

A. To insert new nodes into the BST

B. To balance the BST automatically

C. To delete nodes from the BST

D. To traverse the BST in ascending order without recursion

Solution

1. Step 1: Understand BST Iterator functionality

   A BST Iterator is designed to traverse the tree in sorted order, usually ascending, without using recursion explicitly.

2. Step 2: Identify the main purpose

   Among the options, only traversing in ascending order without recursion matches the BST Iterator's role.

3. Final Answer:

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

4. Quick Check:

   BST Iterator = In-order traversal without recursion [OK]

Hint: BST Iterator helps traverse nodes in sorted order easily [OK]

Common Mistakes:

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

2. Which of the following is the correct C# method signature for the Next() method in a BST Iterator class that returns the next smallest integer?

easy

A. public string Next()

B. public void Next()

C. public int Next()

D. public bool Next()

Solution

1. Step 1: Determine the return type of Next()

   The Next() method should return the next smallest integer value from the BST, so its return type must be int.

2. Step 2: Check method signature correctness

   Only public int Next() matches the expected signature returning an integer value.

3. Final Answer:

   public int Next() -> Option C

4. Quick Check:

   Next() returns int value [OK]

Hint: Next() returns the next smallest value as int [OK]

Common Mistakes:

• Using void return type for Next()
• Returning bool instead of int
• Returning string instead of int

3. Given the BST with nodes inserted in this order: 7, 3, 15, 9, 20. What is the output sequence of calling Next() five times on a correctly implemented BST Iterator?

medium

A. [7, 3, 15, 9, 20]

B. [3, 7, 9, 15, 20]

C. [20, 15, 9, 7, 3]

D. [3, 9, 7, 15, 20]

Solution

1. Step 1: Construct BST and find in-order traversal

   Inserting 7, 3, 15, 9, 20 creates BST:
   7 is root
   3 left of 7
   15 right of 7
   9 left of 15
   20 right of 15
   In-order traversal (left-root-right) is [3, 7, 9, 15, 20].

2. Step 2: Understand Next() output sequence

   Calling Next() five times returns nodes in in-order sequence: 3, 7, 9, 15, 20.

3. Final Answer:

   [3, 7, 9, 15, 20] -> Option B

4. Quick Check:

   In-order traversal = Next() outputs [3,7,9,15,20] [OK]

Hint: Next() outputs nodes in ascending order [OK]

Common Mistakes:

• Confusing insertion order with traversal order
• Reversing the output sequence
• Mixing left and right subtree nodes

4. Identify the bug in this BST Iterator Next() method snippet and choose the correct fix:

public int Next() {
    TreeNode node = stack.Pop();
    if (node.right != null) {
        stack.Push(node.right);
    }
    return node.val;
}

medium

A. Push all left children of node.right onto stack, not just node.right

B. Pop from stack only if it is not empty

C. Return node.val before popping from stack

D. Check node.left instead of node.right

Solution

1. Step 1: Analyze the Next() method logic

   After popping node, if node.right exists, we must push node.right and all its left descendants to maintain in-order traversal.

2. Step 2: Identify missing step

   Current code pushes only node.right, missing its left subtree nodes, causing incorrect traversal order.

3. Final Answer:

   Push all left children of node.right onto stack, not just node.right -> Option A

4. Quick Check:

   Push left subtree nodes after right child [OK]

Hint: Always push left children of right subtree after popping [OK]

Common Mistakes:

• Pushing only right child without left descendants
• Returning value before popping
• Checking left child instead of right child

5. You want to design a BST Iterator that supports HasNext() and Next() methods with O(1) average time per call and O(h) space, where h is tree height. Which approach best achieves this?

hard

A. Use a stack to store left children nodes and push left descendants of right child on Next()

B. Store all nodes in a list during initialization and iterate over the list

C. Use recursion inside Next() to find next node each time

D. Use a queue to store nodes in level order traversal

Solution

1. Step 1: Understand time and space constraints

   O(1) average time per call and O(h) space means we cannot store all nodes upfront or use recursion each call.

2. Step 2: Evaluate approaches

   Using a stack to store left children and pushing left descendants of right child on Next() achieves these constraints efficiently.

3. Final Answer:

   Use a stack to store left children nodes and push left descendants of right child on Next() -> Option A

4. Quick Check:

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

Hint: Stack with left children keeps O(h) space and O(1) average time [OK]

Common Mistakes:

• Storing all nodes wastes O(n) space
• Using recursion causes higher time complexity
• Using queue breaks in-order traversal order