BST Iterator Design in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Iterator next() calls

Given the BST Iterator initialized with the BST below, what is the output sequence of calling next() four times?

DSA Rust

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

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

// Iterator initialized with root node 7

A [3, 7, 9, 15]

B [7, 3, 9, 15]

C [3, 7, 15, 9]

D [7, 9, 15, 20]

💡 Hint

Remember that BST Iterator returns nodes in ascending order (in-order traversal).

The BST Iterator returns nodes in ascending order. The in-order traversal of the tree is 3, 7, 9, 15, 20. Calling next() four times returns the first four values in this order.

🧠 Conceptual

intermediate

BST Iterator Space Complexity

What is the worst-case space complexity of a BST Iterator that uses a stack to simulate in-order traversal on a BST with n nodes?

A O(n^2), due to repeated stack operations

B O(n), when the BST is skewed

C O(1), because it uses constant extra space

D O(log n), always

💡 Hint

Consider the shape of the BST and how many nodes can be on the stack at once.

The stack stores nodes from the root to the current node. In the worst case, if the BST is skewed (like a linked list), the stack can hold all n nodes, so space complexity is O(n).

🔧 Debug

advanced

Identify the bug in BST Iterator next() method

What error will the following Rust code cause when calling next() on the BST Iterator if the stack is empty?

DSA Rust

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

A Returns None instead of i32

B Infinite loop due to wrong while condition

C panic! at unwrap() on empty stack

D Compilation error due to missing lifetime annotations

💡 Hint

What happens if pop() is called on an empty vector and unwrap() is used?

If the stack is empty, calling pop() returns None. Using unwrap() on None causes a panic at runtime.

📝 Syntax

advanced

Correct Rust syntax for BST Iterator initialization

Which option correctly initializes the stack with all left children of the root node in a BST Iterator constructor in Rust?

DSA Rust

fn new(root: Option<Box<TreeNode>>) -> Self {
    let mut stack = Vec::new();
    let mut current = root;
    // Fill stack with left children
    while let Some(node) = current {
        // ???
    }
    BSTIterator { stack }
}

A stack.push(*node); current = node.left;

B stack.push(node); current = node.left.clone();

C stack.push(node.clone()); current = node.left;

D stack.push(node.clone()); current = node.left.clone();

💡 Hint

Remember to clone the node when pushing to the stack before moving to the left child to avoid ownership errors.

In Rust, clone the node to push onto the stack since the loop consumes ownership of the node when moving to its left child (current = node.left.clone()).

🚀 Application

expert

Number of next() calls to exhaust BST Iterator

Given a BST with 10 nodes, how many times can next() be called on a correctly implemented BST Iterator before hasNext() returns false?

A 10

B 9

C 11

D Depends on the shape of the BST

💡 Hint

Each next() call returns one node in the BST in ascending order.

The BST Iterator returns each node exactly once. For 10 nodes, next() can be called 10 times before no nodes remain.

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