BST Iterator Design in DSA Rust - Execution Trace

Concept Flow - BST Iterator Design

Initialize stack

↓

Push all left nodes from root

↓

HasNext?

↓

Pop top node

↓

End

↓

Return node value

↓

Push all left nodes from popped node's right child

↓

Repeat HasNext?

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

Execution Sample

DSA Rust

struct BSTIterator {
    stack: Vec<TreeNode>,
}

fn next(&mut self) -> i32 {
    let node = self.stack.pop().unwrap();
    push_left(&mut self.stack, node.right);
    node.val
}

This code pops the top node from the stack, pushes all left children of its right subtree, and returns the node's value.

Execution Table

Step	Operation	Nodes in Stack (top to bottom)	Pointer Changes	Visual State
1	Initialize stack and push left from root (7)	[3, 5, 7]	Push 7, then 5, then 3	Stack: 3(top) -> 5 -> 7 -> null
2	HasNext? Check stack not empty	[3, 5, 7]	No change	Stack unchanged
3	Pop top node (3)	[5, 7]	Pop 3	Stack: 5(top) -> 7 -> null; Return 3
4	Push left from popped node's right child (3.right = null)	[5, 7]	No push	Stack unchanged
5	HasNext? Check stack not empty	[5, 7]	No change	Stack unchanged
6	Pop top node (5)	[7]	Pop 5	Stack: 7(top) -> null; Return 5
7	Push left from popped node's right child (5.right = 6)	[6, 7]	Push 6	Stack: 6(top) -> 7 -> null
8	HasNext? Check stack not empty	[6, 7]	No change	Stack unchanged
9	Pop top node (6)	[7]	Pop 6	Stack: 7(top) -> null; Return 6
10	Push left from popped node's right child (6.right = null)	[7]	No push	Stack unchanged
11	HasNext? Check stack not empty	[7]	No change	Stack unchanged
12	Pop top node (7)	[]	Pop 7	Stack empty; Return 7
13	Push left from popped node's right child (7.right = 15)	[15]	Push 15	Stack: 15(top) -> null
14	HasNext? Check stack not empty	[15]	No change	Stack unchanged
15	Pop top node (15)	[]	Pop 15	Stack empty; Return 15
16	Push left from popped node's right child (15.right = null)	[]	No push	Stack unchanged
17	HasNext? Check stack not empty	[]	No change	Stack empty, iteration ends

💡 Stack is empty, no more nodes to visit

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	After Step 9	After Step 12	After Step 15	Final
stack	[]	[3,5,7]	[5,7]	[6,7]	[7]	[]	[]	[]
current_node	null	null	3	5	6	7	15	null
returned_value	null	null	3	5	6	7	15	null

Key Moments - 3 Insights

Why do we push all left children when initializing and after popping a node?

Because the smallest values are always on the left, pushing all left children ensures the next smallest node is on top of the stack, as shown in steps 1 and 13 in the execution_table.

What happens if the popped node has no right child?

No new nodes are pushed to the stack, so the stack size decreases, as seen in steps 4 and 10 where no push occurs after popping nodes with no right child.

Why does the stack sometimes have multiple nodes and sometimes only one?

The stack holds the path of nodes to visit next. When pushing left children of a right subtree, multiple nodes can be added. When no right child exists, the stack shrinks.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the top node in the stack after popping?

A 3

B 5

C 7

D 6

💡 Hint

Check the 'Nodes in Stack' column at step 3 in execution_table

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

A Step 12

B Step 15

C Step 17

D Step 9

💡 Hint

Look at the 'Nodes in Stack' column for empty list [] in execution_table

If the node 5 had no right child, how would the stack change after step 6?

A Stack would become empty

B Stack would add node 6

C Stack would remain [7]

D Stack would add node 3

💡 Hint

Refer to step 7 where pushing left children of 5.right happens; if 5.right is null, no push occurs

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, returns its value, then pushes all left children of popped node's right child.
hasNext() checks if stack is not empty.
This simulates in-order traversal with O(h) space, h = tree height.

Full Transcript

The BST Iterator design uses a stack to simulate in-order traversal of a binary search tree. Initially, it pushes all left nodes from the root onto the stack. When next() is called, it 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 checks if the stack is empty to determine if more nodes remain. This approach ensures nodes are returned in ascending order with efficient space usage proportional to the tree height.

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.

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 = Ascending traversal [OK]

Hint: BST Iterator returns next smallest element in order [OK]

Common Mistakes:

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

2. Which of the following Rust code snippets correctly declares a struct for a BST Iterator holding a stack of nodes?

easy

A. struct BSTIterator { stack: Vec<&TreeNode> }

B. struct BSTIterator { stack: Vec<TreeNode> }

C. struct BSTIterator { stack: Vec> }

D. struct BSTIterator { stack: Vec }

Solution

1. Step 1: Understand ownership in Rust for tree nodes

   Tree nodes are usually boxed to allow recursive types. The iterator needs ownership or mutable access, so using Vec is correct.

2. Step 2: Analyze options

   struct BSTIterator { stack: Vec } uses Vec, which is correct. struct BSTIterator { stack: Vec<TreeNode> } uses Vec<TreeNode> which is invalid due to recursive type size. struct BSTIterator { stack: Vec<&TreeNode> } uses references which complicate lifetimes. struct BSTIterator { stack: Vec> } uses Option unnecessarily.

3. Final Answer:

   struct BSTIterator { stack: Vec } -> Option D

4. Quick Check:

   Use Box for recursive nodes in Vec [OK]

Hint: Use Box to store recursive tree nodes in Vec [OK]

Common Mistakes:

• Using Vec<TreeNode> causes size errors
• Using references without lifetimes
• Wrapping nodes in Option unnecessarily

3. Given the following Rust code for a BST Iterator, what will be printed after calling next() twice?

let mut iter = BSTIterator::new(root);
println!("{}", iter.next().unwrap());
println!("{}", iter.next().unwrap());

Assuming the BST contains nodes with values 3, 7, 9 in sorted order.

medium

A. 9
7

B. 7
9

C. 3
7

D. 3
9

Solution

1. Step 1: Understand BST Iterator traversal order

   The iterator returns nodes in ascending order: 3, then 7, then 9.

2. Step 2: Trace the two next() calls

   First next() returns 3, second next() returns 7.

3. Final Answer:

   3 7 -> Option C

4. Quick Check:

   Next returns ascending values [OK]

Hint: next() returns smallest remaining node [OK]

Common Mistakes:

• Assuming next() returns largest first
• Mixing up order of traversal
• Ignoring unwrap() usage

4. Consider this Rust code snippet for BST Iterator's next() method:

fn next(&mut self) -> Option<i32> {
    let node = self.stack.pop()?;
    let val = node.val;
    let mut current = node.right;
    while let Some(n) = current {
        self.stack.push(n);
        current = n.left;
    }
    Some(val)
}

What is the bug in this code?

medium

A. It pushes nodes in wrong order causing incorrect traversal

B. It does not handle empty stack correctly

C. It moves current incorrectly causing infinite loop

D. It pushes nodes without boxing causing ownership errors

Solution

1. Step 1: Analyze node pushing order in while loop

   The code pushes nodes while moving left, but it pushes current node before going left, which reverses order and breaks in-order traversal.

2. Step 2: Identify correct pushing order

   Nodes should be pushed starting from leftmost node upwards, so pushing before moving left causes wrong order.

3. Final Answer:

   It pushes nodes in wrong order causing incorrect traversal -> Option A

4. Quick Check:

   Push left nodes in correct order [OK]

Hint: Push left children before moving left to maintain order [OK]

Common Mistakes:

• Ignoring order of stack pushes
• Assuming pop handles empty stack safely
• Confusing ownership with traversal logic

5. You want to design a BST Iterator in Rust that supports peek() to see the next smallest element without advancing the iterator. Which approach is best to implement peek() efficiently?

hard

A. Traverse the entire BST and store all elements in a vector upfront

B. Store the next smallest element in a variable updated on each next() call

C. Use recursion inside peek() to find the next element every time

D. Modify the BST structure to add parent pointers for easy access

Solution

1. Step 1: Understand peek() requirement

   Peek should return next smallest element without moving iterator forward, so it needs to know next element in advance.

2. Step 2: Evaluate approaches

   Store the next smallest element in a variable updated on each next() call keeps next element cached and updates it on next(), making peek() O(1). Traverse the entire BST and store all elements in a vector upfront uses extra memory and upfront cost. Use recursion inside peek() to find the next element every time is inefficient due to repeated traversal. Modify the BST structure to add parent pointers for easy access complicates BST unnecessarily.

3. Final Answer:

   Store the next smallest element in a variable updated on each next() call -> Option B

4. Quick Check:

   Cache next element for O(1) peek [OK]

Hint: Cache next element to peek without advancing [OK]

Common Mistakes:

• Recomputing next element on every peek
• Storing entire traversal upfront wasting memory
• Changing BST structure unnecessarily