BST Iterator Design in DSA Rust - Time & Space Complexity

Time Complexity: BST Iterator Design

O(1) amortized

Understanding Time Complexity

We want to understand how fast the BST Iterator works when we use it to get the next smallest value.

How does the time to get the next value change as the tree grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct BSTIterator {
    stack: Vec<TreeNode>,
}

impl BSTIterator {
    fn new(root: Option<Box<TreeNode>>) -> Self {
        let mut it = BSTIterator { stack: Vec::new() };
        it.push_left(root);
        it
    }

    fn push_left(&mut self, mut node: Option<Box<TreeNode>>) {
        while let Some(n) = node {
            let mut tree_node = *n;
            let left = tree_node.left.take();
            self.stack.push(tree_node);
            node = left;
        }
    }

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

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

This code creates an iterator over a binary search tree that returns the next smallest value each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop inside push_left that pushes left children onto the stack.
• How many times: Each node is pushed and popped exactly once during the entire iteration.

How Execution Grows With Input

Getting the next value usually takes a small number of steps, but sometimes it takes more when moving down the left side of a subtree.

Input Size (n)	Approx. Operations per next()
10	About 1 to 3 steps
100	About 1 to 7 steps
1000	About 1 to 10 steps

Pattern observation: Most calls to next() do a quick pop, but some do extra work pushing left children. Over all calls, work spreads evenly.

Final Time Complexity

Time Complexity: O(1) amortized

This means each call to next() takes constant time on average, even if some calls take longer.

Common Mistake

[X] Wrong: "Each call to next() always takes time proportional to the tree height."

[OK] Correct: Because the extra work of pushing left children is spread out over many calls, so on average each call is fast.

Interview Connect

Understanding this amortized time complexity shows you can analyze how repeated operations share work over time, a key skill in coding interviews.

Self-Check

What if we changed the iterator to store all nodes in a sorted list at the start? How would the time complexity of next() change?

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