BST Find Minimum Element in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the minimum element in a Binary Search Tree (BST)?

The minimum element in a BST is the leftmost node because all smaller values are stored to the left.

beginner

How do you find the minimum element in a BST?

Start at the root and keep moving to the left child until you reach a node with no left child. That node is the minimum.

intermediate

Why does the minimum element in a BST always lie in the left subtree?

Because BST property states left child nodes have smaller values than their parents, so the smallest value is found by going left repeatedly.

intermediate

Rust code snippet to find minimum element in a BST node:

fn find_min(node: &Option) -> Option<i32> { match node { Some(n) => { if n.left.is_none() { Some(n.val) } else { find_min(&n.left) } } None => None, } }

beginner

What happens if you call find_min on an empty BST?

The function returns None because there is no node to find a minimum value from.

Where is the minimum element located in a BST?

A Rightmost node

B Any leaf node

C Root node

D Leftmost node

The minimum element is always the leftmost node in a BST.

What is the first step to find the minimum element in a BST?

A Go to the right child

B Go to the left child

C Check the root value

D Traverse all nodes

You start at the root and move to the left child repeatedly to find the minimum.

If a BST node has no left child, what does that node represent?

A Minimum element

B Leaf node

C Root node

D Maximum element

A node with no left child is the minimum element in that subtree.

What does the Rust function find_min return if the BST is empty?

A None

B Some(minimum value)

C Some(0)

D Panic error

It returns None because there is no node to find a minimum value.

Why is it efficient to find the minimum element in a BST?

A Because BST is balanced

B Because you check all nodes

C Because you only traverse left children

D Because minimum is always root

You only move left until no left child exists, so it is efficient.

Explain how to find the minimum element in a Binary Search Tree.

Think about the BST property and left children.

Write a simple Rust function to find the minimum element in a BST and explain its logic.

Use Option and pattern matching.

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