BST Iterator Design in DSA Rust - Build from Scratch

BST Iterator Design

📖 Scenario: You are building a tool to explore a collection of numbers stored in a special tree called a Binary Search Tree (BST). This tree keeps numbers in order, so you can find the smallest number quickly and then move to the next bigger number step by step.Imagine you have a bookshelf where books are arranged by height. You want to look at the books from shortest to tallest without rearranging the shelf. The BST iterator helps you do this with numbers in the tree.

🎯 Goal: Build a BST Iterator in Rust that lets you look at the numbers in the tree one by one in increasing order. You will create the tree, set up the iterator, write the logic to move through the tree, and finally print the numbers in order.

📋 What You'll Learn

Create a BST with the exact nodes given

Create a stack to help with the iterator

Implement the iterator methods to get the next smallest number

Print the numbers in ascending order using the iterator

💡 Why This Matters

🌍 Real World

BST iterators are used in databases and search engines to efficiently access sorted data without loading everything into memory at once.

💼 Career

Understanding BST iterators helps in roles involving data structure design, algorithm optimization, and systems programming where efficient data traversal is critical.

1

Create the BST nodes

Create a struct called TreeNode with fields val: i32, left: Option>, and right: Option>. Then create a BST with root node value 7, left child 3, and right child 15. The right child 15 should have two children: left child 9 and right child 20. Store the root in a variable called root.

DSA Rust

# Define TreeNode struct and create the BST root
# Your code here

Hint

Define the TreeNode struct first. Then build the tree from bottom up using Box::new(TreeNode { ... }) and Some for children.

2

Set up the BSTIterator struct with a stack

Create a struct called BSTIterator with a field stack of type Vec>. Then write an impl block for BSTIterator with a function new that takes root: Option> and returns Self. Inside new, create an empty stack and push all left children of root onto the stack. Store the stack in the struct.

DSA Rust

struct BSTIterator {
    stack: Vec>,
}

impl BSTIterator {
    fn new(root: Option>) -> Self {
        let mut stack = Vec::new();
        // Push all left children of root onto stack
        // Your code here
        BSTIterator { stack }
    }
}

Hint

Use a while let Some(node) = root loop to push all left nodes onto the stack. Update root to node.left each time.

3

Implement next() and has_next() methods

Inside the impl BSTIterator block, write a method next(&mut self) -> i32 that pops the top node from the stack, pushes all left children of its right child onto the stack, and returns the popped node's value. Also write a method has_next(&self) -> bool that returns true if the stack is not empty, otherwise false.

DSA Rust

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

let root = Some(Box::new(TreeNode {
    val: 7,
    left: Some(Box::new(TreeNode {
        val: 3,
        left: None,
        right: None,
    })),
    right: Some(Box::new(TreeNode {
        val: 15,
        left: Some(Box::new(TreeNode {
            val: 9,
            left: None,
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 20,
            left: None,
            right: None,
        })),
    })),
}));

struct BSTIterator {
    stack: Vec>,
}

impl BSTIterator {
    fn new(mut root: Option>) -> Self {
        let mut stack = Vec::new();
        while let Some(node) = root {
            root = node.left;
            stack.push(node);
        }
        BSTIterator { stack }
    }

    fn next(&mut self) -> i32 {
        // Your code here
    }

    fn has_next(&self) -> bool {
        // Your code here
    }
}

Hint

In next, pop the top node, then push all left children of its right child onto the stack. Return the popped node's value. In has_next, check if the stack is empty.

4

Use the BSTIterator to print all values in ascending order

Create a mutable variable iterator by calling BSTIterator::new(root). Then use a while loop that runs while iterator.has_next() is true. Inside the loop, print the value returned by iterator.next() followed by a space. This will print all values in ascending order.

DSA Rust

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

let root = Some(Box::new(TreeNode {
    val: 7,
    left: Some(Box::new(TreeNode {
        val: 3,
        left: None,
        right: None,
    })),
    right: Some(Box::new(TreeNode {
        val: 15,
        left: Some(Box::new(TreeNode {
            val: 9,
            left: None,
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 20,
            left: None,
            right: None,
        })),
    })),
}));

struct BSTIterator {
    stack: Vec>,
}

impl BSTIterator {
    fn new(mut root: Option>) -> Self {
        let mut stack = Vec::new();
        while let Some(node) = root {
            root = node.left;
            stack.push(node);
        }
        BSTIterator { stack }
    }

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

    fn has_next(&self) -> bool {
        !self.stack.is_empty()
    }
}

// Your code here

Hint

Create the iterator with BSTIterator::new(root). Use a while loop with iterator.has_next(). Inside the loop, print iterator.next() followed by a space.

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