BST Iterator Design in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the stack in the BST iterator constructor.

DSA Rust

fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
    let mut stack = Vec::new();
    let mut current = root;
    while let Some(node) = current {
        stack.push(node.clone());
        current = node.borrow().[1];
    }
    BSTIterator { stack }
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cnext

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Using right child instead of left child.

Trying to access a non-existent parent pointer.

The iterator pushes all left children to the stack initially to start with the smallest element.

2fill in blank

medium

Complete the code to check if the iterator has a next element.

DSA Rust

fn has_next(&self) -> bool {
    !self.stack.[1]()
}

Drag options to blanks, or click blank then click option'

Ais_empty

Blen

Cpop

Dpeek

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop which removes elements.

Using len which returns a number instead of a boolean.

has_next returns true if the stack is not empty, so we check if it is empty and negate the result.

3fill in blank

hard

Fix the error in the next() method to correctly push left children of the right subtree.

DSA Rust

fn next(&mut self) -> i32 {
    let node = self.stack.pop().unwrap();
    let mut current = node.borrow().[1].clone();
    while let Some(n) = current {
        self.stack.push(n.clone());
        current = n.borrow().[2];
    }
    node.borrow().val
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cparent

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using left child instead of right child for current initialization.

Using right child instead of left child inside the loop.

After popping the node, we move to its right child and push all left children of that subtree onto the stack.

4fill in blank

hard

Fill both blanks to complete the BSTIterator struct and implement the constructor.

DSA Rust

struct BSTIterator {
    stack: Vec<Rc<RefCell<TreeNode>>>,
}

impl BSTIterator {
    fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
        let mut stack = Vec::new();
        let mut current = root;
        while let Some(node) = current {
            stack.push(node.clone());
            current = node.borrow().[1];
        }
        BSTIterator { [2] }
    }
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cstack

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Returning current instead of stack.

Using right child instead of left child.

The stack stores nodes for iteration, and we initialize it by pushing left children. The struct field is named stack.

5fill in blank

hard

Fill all three blanks to complete the next() method of BSTIterator.

DSA Rust

fn next(&mut self) -> i32 {
    let node = self.stack.pop().unwrap();
    let mut current = node.borrow().[1].clone();
    while let Some(n) = current {
        self.stack.push(n.clone());
        current = n.borrow().[2];
    }
    node.borrow().[3]
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cval

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Returning the parent instead of the value.

Using left child instead of right child for current initialization.

We start from the right child of the popped node, push all left children, and finally return the node's value.

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