BST Iterator Design in DSA C - 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 track nodes. It pushes all left children from the root initially. Each next() pops the top node, returns its value, then pushes all left children of the popped node's right child.

Execution Sample

DSA C

void pushLeft(TreeNode* node) {
  while (node != NULL) {
    stack_push(node);
    node = node->left;
  }
}

int next() {
  TreeNode* top = stack_pop();
  pushLeft(top->right);
  return top->val;
}

This code pushes all left nodes starting from a given node onto the stack, then next() pops the top node, pushes left nodes of its right child, and returns the popped node's value.

Execution Table

Step	Operation	Nodes in Stack (top to bottom)	Pointer Changes	Visual State (BST nodes with stack top)
1	Initialize stack empty	[]	stack = []	BST unchanged, stack empty
2	Push all left from root (10)	[3, 7, 10]	stack_push(10), stack_push(7), stack_push(3)	Stack top=3, BST root=10 10 / \ 7 15 / \ \ 3 9 20
3	next() called - pop top	[7, 10]	pop 3	Pop node 3, stack top=7
4	Return 3	[7, 10]	return 3	Returned value=3
5	Push all left from popped node's right (3->right=NULL)	[7, 10]	No push	Stack unchanged
6	next() called - pop top	[10]	pop 7	Pop node 7, stack top=10
7	Return 7	[10]	return 7	Returned value=7
8	Push all left from popped node's right (7->right=9)	[9, 10]	push 9	Stack top=9
9	next() called - pop top	[10]	pop 9	Pop node 9, stack top=10
10	Return 9	[10]	return 9	Returned value=9
11	Push all left from popped node's right (9->right=NULL)	[10]	No push	Stack unchanged
12	next() called - pop top	[]	pop 10	Pop node 10, stack empty
13	Return 10	[]	return 10	Returned value=10
14	Push all left from popped node's right (10->right=15)	[15]	push 15	Stack top=15
15	next() called - pop top	[]	pop 15	Pop node 15, stack empty
16	Return 15	[]	return 15	Returned value=15
17	Push all left from popped node's right (15->right=20)	[20]	push 20	Stack top=20
18	next() called - pop top	[]	pop 20	Pop node 20, stack empty
19	Return 20	[]	return 20	Returned value=20
20	Push all left from popped node's right (20->right=NULL)	[]	No push	Stack empty
21	next() called - pop top	[]	stack empty, no pop	No next element, iteration ends

💡 Stack becomes empty after all nodes are visited, no next element available.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	After Step 14	After Step 16	After Step 18	Final
stack	[]	[3,7,10]	[7,10]	[10]	[9,10]	[10]	[]	[15]	[]	[]	[]
current_node	root=10	10	3	7	9	9	10	15	15	20	NULL
returned_value	N/A	N/A	3	7	9	9	10	15	15	20	N/A

Key Moments - 3 Insights

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

Because in BST inorder traversal, after visiting a node, we must visit its right subtree starting from the leftmost node. This is shown in execution_table steps where pushLeft is called on the popped node's right child.

Why does the stack initially contain multiple nodes before any next() calls?

The stack initially holds all left children from the root to ensure the smallest element is on top. This is shown in step 2 where nodes 10, 7, and 3 are pushed, with 3 on top.

What happens when the stack becomes empty?

When the stack is empty, there are no more nodes to visit in inorder. This is shown in the final step where next() cannot pop any node and iteration ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what value is returned by next()?

A 3

B 7

C 9

D 10

💡 Hint

Check the 'Returned value' column at step 4 in execution_table.

At which step does the stack become empty for the first time?

A Step 11

B Step 12

C Step 10

D Step 9

💡 Hint

Look at the 'Nodes in Stack' column in execution_table to find when it becomes [].

If the BST had no left children, how would the initial stack look after step 2?

A Empty stack []

B Stack with all nodes [root, right child, right-right child]

C Stack with root only [root]

D Stack with all nodes in inorder

💡 Hint

Recall pushLeft pushes left children only; if none, only root is pushed.

Concept Snapshot

BST Iterator uses a stack to simulate inorder traversal.
Initialize by pushing all left nodes from root.
next() pops top node, returns its value,
and pushes all left nodes from popped node's right child.
hasNext() checks if stack is empty.

Full Transcript

The BST Iterator design uses a stack to traverse the tree in sorted order without recursion. Initially, all left children from the root are pushed 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 from the popped node's right child. This process continues until the stack is empty, meaning all nodes have been visited. The stack always holds the path to the next smallest node. This approach efficiently supports hasNext() and next() operations in O(1) average time.

Practice

1. What is the main purpose of a BST Iterator in a binary search tree?

easy

A. To delete nodes from the BST

B. To insert new nodes into the BST

C. To balance the BST automatically

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, 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 D

4. Quick Check:

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

Hint: BST Iterator returns next smallest element in sorted order [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 declare a stack for implementing a BST Iterator in C?

easy

A. int stack[100]; int top = -1;

B. stack<int> s; // C++ syntax

C. List<int> stack = new List<int>();

D. var stack = [];

Solution

1. Step 1: Identify language and syntax

   The question is about C language, so C++ or other language syntax is invalid.

2. Step 2: Choose correct C stack declaration

   int stack[100]; int top = -1; declares a fixed-size integer array and a top index, which is the typical way to implement a stack in C.

3. Final Answer:

   int stack[100]; int top = -1; -> Option A

4. Quick Check:

   C stack = array + top index [OK]

Hint: Use array and top index for stack in C [OK]

Common Mistakes:

• Using C++ or other language syntax in C
• Using dynamic lists not available in C
• Using var keyword which is not in C

3. Consider the following BST Iterator code snippet in C. What will be the output sequence of next() calls?

typedef struct Node {
  int val;
  struct Node* left;
  struct Node* right;
} Node;

// Assume stack and top are global
void push(Node* node) { stack[++top] = node; }
Node* pop() { return stack[top--]; }

void pushLeft(Node* root) {
  while (root) {
    push(root);
    root = root->left;
  }
}

Node* next() {
  Node* node = pop();
  pushLeft(node->right);
  return node;
}

// BST structure:
//       5
//      / \
//     3   7
//    / \   \
//   2   4   8

// Initial call: pushLeft(root) where root = 5

// Calls: next(), next(), next(), next(), next(), next()

medium

A. [2, 4, 3, 5, 8, 7]

B. [5, 3, 2, 4, 7, 8]

C. [2, 3, 4, 5, 7, 8]

D. [8, 7, 5, 4, 3, 2]

Solution

1. Step 1: Understand pushLeft and next behavior

   pushLeft pushes all left children starting from root. next pops top node, then pushes left children of right subtree.

2. Step 2: Trace calls step-by-step

   Initial stack after pushLeft(5): [5,3,2] (top is 2). next() pops 2 (no right child), output 2.
   next() pops 3, pushes left of 4 (which is 4), output 3.
   next() pops 4 (no right child), output 4.
   next() pops 5, pushes left of 7 (which is 7), output 5.
   next() pops 7, pushes left of 8 (which is 8), output 7.
   next() pops 8, output 8.

3. Final Answer:

   [2, 3, 4, 5, 7, 8] -> Option C

4. Quick Check:

   In-order traversal = [2,3,4,5,7,8] [OK]

Hint: Trace stack push/pop for in-order sequence [OK]

Common Mistakes:

• Ignoring pushLeft on right child
• Assuming preorder or postorder output
• Mixing up stack order

4. The following code snippet for BST Iterator has a bug. What is the error?

typedef struct Node {
  int val;
  struct Node* left;
  struct Node* right;
} Node;

Node* stack[100];
int top = -1;

void push(Node* node) { stack[++top] = node; }
Node* pop() { return stack[top--]; }

void pushLeft(Node* root) {
  while (root != NULL) {
    push(root);
    root = root->left;
  }
}

Node* next() {
  Node* node = pop();
  pushLeft(node->right);
  return node;
}

int hasNext() {
  return top >= 0;
}

// Usage:
// pushLeft(root);
// while (hasNext()) {
//   Node* n = next();
//   printf("%d ", n->val);
// }

medium

A. pop() returns NULL when stack is empty causing crash

B. Stack overflow if BST is large and pushLeft pushes too many nodes

C. pushLeft does not handle NULL root correctly

D. hasNext() returns wrong boolean value

Solution

1. Step 1: Analyze stack usage in pushLeft

   pushLeft pushes all left nodes onto stack. For a very deep BST, this can exceed stack size 100 causing overflow.

2. Step 2: Check other functions for errors

   pop() assumes stack not empty; hasNext() correctly checks top >= 0; pushLeft handles NULL root by stopping loop.

3. Final Answer:

   Stack overflow if BST is large and pushLeft pushes too many nodes -> Option B

4. Quick Check:

   Fixed stack size risks overflow [OK]

Hint: Check fixed stack size limits for large BSTs [OK]

Common Mistakes:

• Assuming pop() returns NULL safely
• Thinking pushLeft fails on NULL root
• Believing hasNext() logic is incorrect

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

hard

A. Use a stack to store left children, pushing right subtree nodes on next() calls

B. Store all nodes in an array by in-order 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) memory means no full traversal storage and no recursion per call.

2. Step 2: Evaluate options

   Use a stack to store left children, pushing right subtree nodes on next() calls uses a stack to store left children only, pushing right subtree nodes lazily, matching constraints.
   Store all nodes in an array by in-order traversal at initialization uses O(n) memory, violating O(h).
   Use recursion to traverse nodes on each next() call uses recursion each call, not O(1) average.
   Use a queue to store nodes level by level uses queue level order, not in-order traversal.

3. Final Answer:

   Use a stack to store left children, pushing right subtree nodes on next() calls -> Option A

4. Quick Check:

   Stack + lazy push = O(1) avg time & O(h) space [OK]

Hint: Stack with lazy right pushes fits O(1) avg time and O(h) space [OK]

Common Mistakes:

• Precomputing all nodes wastes memory
• Using recursion each next() call is slow
• Using queue gives wrong traversal order