BST Find Minimum Element in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find minimum element in a BST

What is the output of this Rust code that finds the minimum element in a Binary Search Tree (BST)?

DSA Rust

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

impl Node {
    fn find_min(&self) -> i32 {
        match &self.left {
            Some(left_node) => left_node.find_min(),
            None => self.val,
        }
    }
}

fn main() {
    let bst = Node {
        val: 10,
        left: Some(Box::new(Node {
            val: 5,
            left: Some(Box::new(Node { val: 2, left: None, right: None })),
            right: None,
        })),
        right: Some(Box::new(Node { val: 15, left: None, right: None })),
    };
    println!("{}", bst.find_min());
}

A 2

B 5

C 15

D 10

💡 Hint

The minimum element in a BST is the leftmost node.

The code recursively goes to the left child until it finds a node with no left child. That node's value is the minimum.

Here, the leftmost node has value 2.

❓ Predict Output

intermediate

Output of find_min with single node BST

What will be printed when running this Rust code that finds the minimum element in a BST with only one node?

DSA Rust

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

impl Node {
    fn find_min(&self) -> i32 {
        match &self.left {
            Some(left_node) => left_node.find_min(),
            None => self.val,
        }
    }
}

fn main() {
    let bst = Node {
        val: 42,
        left: None,
        right: None,
    };
    println!("{}", bst.find_min());
}

A Compilation error

B 42

C None

D 0

💡 Hint

If there is no left child, the current node's value is returned.

Since the BST has only one node with value 42 and no left child, find_min() returns 42.

🔧 Debug

advanced

Identify the error in this BST minimum finder

What error will this Rust code produce when trying to find the minimum element in a BST?

DSA Rust

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

impl Node {
    fn find_min(&self) -> i32 {
        if self.left.is_some() {
            self.left.as_ref().unwrap().find_min()
        } else {
            self.val
        }
    }
}

fn main() {
    let bst = Node {
        val: 10,
        left: Some(Box::new(Node {
            val: 5,
            left: None,
            right: None,
        })),
        right: None,
    };
    println!("{}", bst.find_min());
}

A Compilation error due to use of unwrap() on Option

B Prints 5 correctly

C Runtime panic due to unwrap() on None value

D Prints 10 incorrectly

💡 Hint

In a &self method, self.left is &Option>. Check if unwrap() can be called on a reference.

The code produces a compilation error. In the &self method, self.left has type &Option<Box<Node>>. The unwrap() method requires ownership (self: Option<T>) to consume the Option and move out the Box<Node>, which cannot be done on a borrow.

To fix, use match &self.left { Some(left_node) => left_node.find_min(), None => self.val } or self.left.as_ref().unwrap().find_min().

🚀 Application

advanced

How many nodes are visited to find minimum in BST?

Given a BST with nodes 20 -> 10 -> 5 -> 2 (each left child), how many nodes does the find_min() function visit to find the minimum?

DSA Rust

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

impl Node {
    fn find_min(&self) -> i32 {
        match &self.left {
            Some(left_node) => left_node.find_min(),
            None => self.val,
        }
    }
}

fn main() {
    let bst = Node {
        val: 20,
        left: Some(Box::new(Node {
            val: 10,
            left: Some(Box::new(Node {
                val: 5,
                left: Some(Box::new(Node { val: 2, left: None, right: None })),
                right: None,
            })),
            right: None,
        })),
        right: None,
    };
    println!("{}", bst.find_min());
}

A 1

B 2

C 3

D 4

💡 Hint

The function visits each left child until none is left.

The find_min() function visits nodes 20, 10, 5, and 2 in order, totaling 4 nodes.

🧠 Conceptual

expert

Why is the leftmost node the minimum in a BST?

Why does the minimum element in a Binary Search Tree (BST) always lie in the leftmost node?

A Because the right subtree always contains larger values, so minimum must be on the rightmost node.

B Because the root node always holds the minimum value in a BST.

C Because BST property ensures all left children are smaller than their parents, so the leftmost node is smallest.

D Because BSTs store values in random order, so minimum is always the leftmost node by chance.

💡 Hint

Recall the BST property about left and right children values.

By definition, in a BST, all nodes in the left subtree have smaller values than the parent node. Recursively, the leftmost node has no left child and is the smallest.

Practice

1. In a Binary Search Tree (BST), where is the minimum element always located?

easy

A. At the leftmost node

B. At the rightmost node

C. At the root node

D. At any leaf node

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes have smaller values than their parents.

2. Step 2: Locate minimum element

   The smallest value is found by going left until no more left child exists.

3. Final Answer:

   At the leftmost node -> Option A

4. Quick Check:

   Minimum element = leftmost node [OK]

Hint: Minimum is always the leftmost node in BST [OK]

Common Mistakes:

• Thinking minimum is at root
• Confusing leftmost with rightmost
• Assuming minimum can be any leaf

2. Which Rust code snippet correctly finds the minimum element in a BST node structure?

easy

A. while let Some(ref left) = current.left { current = left; } current.value

B. while let Some(ref right) = current.right { current = right; } current.value

C. if current.right.is_none() { current.value } else { current.right.as_ref().unwrap().value }

D. if current.left.is_none() { current.value } else { current.right.as_ref().unwrap().value }

Solution

1. Step 1: Traverse left children

   To find minimum, move left while left child exists.

2. Step 2: Return current node's value

   When no left child, current node holds minimum value.

3. Final Answer:

   while let Some(ref left) = current.left { current = left; } current.value -> Option A

4. Quick Check:

   Traverse left until None, then return value [OK]

Hint: Use while let to traverse left children [OK]

Common Mistakes:

• Traversing right instead of left
• Returning wrong node's value
• Using if incorrectly without loop

3. Given this Rust code for a BST node, what will be printed?

struct Node {
    value: i32,
    left: Option,
    right: Option,
}

fn find_min(node: &Node) -> i32 {
    let mut current = node;
    while let Some(ref left) = current.left {
        current = left;
    }
    current.value
}

fn main() {
    let root = Node {
        value: 10,
        left: Some(Box::new(Node {
            value: 5,
            left: Some(Box::new(Node {
                value: 2,
                left: None,
                right: None,
            })),
            right: None,
        })),
        right: None,
    };
    println!("{}", find_min(&root));
}

medium

A. 10

B. 2

C. 5

D. None

Solution

1. Step 1: Traverse left nodes

   Starting at root (10), move left to 5, then left to 2, which has no left child.

2. Step 2: Return value of leftmost node

   Node with value 2 is leftmost, so function returns 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Leftmost node value = 2 [OK]

Hint: Follow left children until None, then return value [OK]

Common Mistakes:

• Returning root value instead of leftmost
• Confusing left and right traversal
• Expecting None instead of value

4. Identify the bug in this Rust function that tries to find the minimum element in a BST:

fn find_min(node: &Node) -> i32 {
    let mut current = node;
    while current.left.is_some() {
        current = current.right.as_ref().unwrap();
    }
    current.value
}

medium

A. It uses unwrap() which can cause panic

B. It does not check if node is None before accessing value

C. It traverses right child instead of left inside the loop

D. It returns current.value before loop

Solution

1. Step 1: Analyze traversal logic

   The loop condition checks if left child exists, but inside loop moves to right child incorrectly.

2. Step 2: Correct traversal direction

   To find minimum, traversal must move to left child, not right.

3. Final Answer:

   It traverses right child instead of left inside the loop -> Option C

4. Quick Check:

   Traverse left child to find minimum [OK]

Hint: Check traversal direction matches condition [OK]

Common Mistakes:

• Mixing left and right child traversal
• Ignoring unwrap panic possibility
• Not checking for None before unwrap

5. You have a BST where some nodes have duplicate values. How would you modify the Rust function to find the minimum unique element?

hard

A. Traverse left until no left child, then skip duplicates by moving right if same value

B. Traverse left until no left child, then check parent nodes for smaller unique values

C. Return the root value as minimum unique element always

D. Traverse entire tree in-order and track minimum unique value

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can appear anywhere; leftmost node may not be unique minimum.

2. Step 2: Use in-order traversal to find minimum unique

   In-order traversal visits nodes in sorted order; track first unique minimum value.

3. Step 3: Implement tracking of unique values

   Keep a set or variable to remember seen values and update minimum unique accordingly.

4. Final Answer:

   Traverse entire tree in-order and track minimum unique value -> Option D

5. Quick Check:

   In-order traversal finds sorted unique minimum [OK]

Hint: Use in-order traversal to find unique minimum [OK]

Common Mistakes:

• Assuming leftmost node is unique minimum
• Ignoring duplicates in traversal
• Returning root value blindly