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.

Practice

1. What is the main purpose of a BST Iterator in the context of a Binary Search Tree?

easy

A. To traverse the BST in ascending order without recursion

B. To insert new nodes into the BST

C. To delete nodes from the BST

D. To balance the BST automatically

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 explicitly.

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 A

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 operations
• Thinking it balances the tree automatically
• Assuming it uses recursion internally

2. Which of the following is the correct way to declare a stack to be used in a BST Iterator in C++?

easy

A. stack s;

B. stack<int> s;

C. stack<TreeNode> s;

D. stack s;

Solution

1. Step 1: Identify the data type stored in the stack

   The BST Iterator stores pointers to tree nodes to traverse the tree efficiently, so the stack should hold TreeNode pointers.

2. Step 2: Match the correct syntax

   stack s; uses stack which is correct. stack<int> s; uses int, which is incorrect. stack<TreeNode> s; uses TreeNode by value, which is inefficient. stack s; uses Node*, which is undefined here.

3. Final Answer:

   stack s; -> Option D

4. Quick Check:

   Stack stores pointers to TreeNode [OK]

Hint: Stack must hold pointers to tree nodes, not values [OK]

Common Mistakes:

• Using stack of int instead of TreeNode*
• Using stack of TreeNode by value causing copies
• Using undefined Node* type

3. Given the following BST Iterator code snippet, what will be the output sequence of calls to next()?

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTIterator {
  stack s;
  void pushLeft(TreeNode* node) {
    while (node) {
      s.push(node);
      node = node->left;
    }
  }
public:
  BSTIterator(TreeNode* root) { pushLeft(root); }
  int next() {
    TreeNode* node = s.top(); s.pop();
    pushLeft(node->right);
    return node->val;
  }
  bool hasNext() { return !s.empty(); }
};

// BST structure:
//       7
//      / \
//     3   15
//         / \
//        9  20

BSTIterator it(root);
while(it.hasNext()) {
  cout << it.next() << " ";
}

medium

A. 20 15 9 7 3

B. 7 3 15 9 20

C. 3 7 9 15 20

D. 3 9 7 15 20

Solution

1. Step 1: Understand the BST structure and in-order traversal

   The BST is: 7 / \ 3 15 / \ 9 20 In-order traversal visits nodes in ascending order: 3, 7, 9, 15, 20.

2. Step 2: Trace the iterator's next() calls

   Iterator pushes left nodes first, so initial stack: 7, 3 (top). Calls to next() pop 3, then 7, then push left of 7's right (15), then 9, then 15, then 20. Output sequence matches 3 7 9 15 20.

3. Final Answer:

   3 7 9 15 20 -> Option C

4. Quick Check:

   In-order traversal = 3 7 9 15 20 [OK]

Hint: BST Iterator outputs nodes in ascending order (in-order) [OK]

Common Mistakes:

• Confusing pre-order or post-order traversal output
• Not pushing left children correctly
• Misunderstanding stack top element order

4. Identify the bug in the following BST Iterator next() method and select the correct fix:

int next() {
  TreeNode* node = s.top();
  s.pop();
  pushLeft(node->left); // Bug here
  return node->val;
}

medium

A. Remove pushLeft call completely

B. Change pushLeft(node->left) to pushLeft(node->right)

C. Change s.pop() to s.pop(node)

D. Add check if node is nullptr before pushLeft

Solution

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

   After popping the current node, the iterator should push all left children of the right subtree to continue in-order traversal.

2. Step 2: Identify the incorrect call

   The code incorrectly calls pushLeft(node->left), which revisits the left subtree already processed. It should call pushLeft(node->right) to process the right subtree.

3. Final Answer:

   Change pushLeft(node->left) to pushLeft(node->right) -> Option B

4. Quick Check:

   Push left of right subtree after pop [OK]

Hint: Push left nodes of right child after popping [OK]

Common Mistakes:

• Pushing left subtree again causing infinite loop
• Removing pushLeft call causing incomplete traversal
• Incorrect pop syntax causing compile error

5. You want to design a BST Iterator that supports a method peek() which returns the next smallest element without advancing the iterator. How would you modify the existing BST Iterator design to support peek() efficiently?

hard

A. Store the next smallest element in a variable during next() and return it in peek()

B. Use an additional stack to store peeked elements separately

C. Modify next() to not pop from stack and peek() to pop instead

D. Precompute all elements in sorted order and store in a vector

Solution

1. Step 1: Understand peek() requirement

   peek() should return next smallest element without moving the iterator forward, so it must remember the next element.

2. Step 2: Modify iterator to store next element

   By storing the next smallest element in a variable during next(), peek() can return this stored value without popping or changing the stack.

3. Step 3: Evaluate other options

   Using an extra stack or precomputing all elements wastes space or changes iterator behavior. Modifying next() to not pop breaks standard iteration.

4. Final Answer:

   Store the next smallest element in a variable during next() and return it in peek() -> Option A

5. Quick Check:

   Cache next element for peek() [OK]

Hint: Cache next element on next() call for peek() [OK]

Common Mistakes:

• Precomputing all elements wastes memory
• Changing next() behavior breaks iteration
• Using extra stack complicates design unnecessarily