BST Find Minimum Element in DSA Rust - Build from Scratch

BST Find Minimum Element

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the smallest number in the tree. This is useful when you want to quickly find the minimum value in a sorted structure.

🎯 Goal: Build a simple BST in Rust and write code to find and print the minimum element in the BST.

📋 What You'll Learn

Create a BST node struct with integer values

Manually create a BST with specific nodes

Write a function to find the minimum element in the BST

Print the minimum element found

💡 Why This Matters

🌍 Real World

Finding the minimum element in a BST is useful in databases and search engines where quick access to sorted data is needed.

💼 Career

Understanding BST operations is important for software engineers working with data structures, algorithms, and performance optimization.

1

Create BST Node Struct and Build Tree

Create a struct called Node with fields value: i32, left: Option>, and right: Option>. Then create a variable called root that represents the root node of the BST with value 10. Add a left child node with value 5 and a right child node with value 15.

DSA Rust

// Define the Node struct and create the root node with children
// Your code here

Hint

Use Option> for left and right children to allow empty branches.

2

Add a Function to Find Minimum Value

Add a function called find_min that takes a reference to a Node and returns the minimum i32 value in the BST. The function should follow the left child nodes until it finds the leftmost node.

DSA Rust

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

fn find_min(node: &Node) -> i32 {
    // Your code here
}

fn main() {
    let root = Node {
        value: 10,
        left: Some(Box::new(Node {
            value: 5,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 15,
            left: None,
            right: None,
        })),
    };
}

Hint

Use recursion to keep going left until there is no left child.

3

Call the Function to Find Minimum

Inside main, create a variable called min_value and set it to the result of calling find_min with a reference to root.

DSA Rust

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

fn find_min(node: &Node) -> i32 {
    match &node.left {
        Some(left_node) => find_min(left_node),
        None => node.value,
    }
}

fn main() {
    let root = Node {
        value: 10,
        left: Some(Box::new(Node {
            value: 5,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 15,
            left: None,
            right: None,
        })),
    };
    // Your code here
}

Hint

Call find_min with &root and store the result in min_value.

4

Print the Minimum Value

Add a println! statement to print the text "Minimum value in BST: " followed by the value of min_value.

DSA Rust

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

fn find_min(node: &Node) -> i32 {
    match &node.left {
        Some(left_node) => find_min(left_node),
        None => node.value,
    }
}

fn main() {
    let root = Node {
        value: 10,
        left: Some(Box::new(Node {
            value: 5,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 15,
            left: None,
            right: None,
        })),
    };
    let min_value = find_min(&root);
    // Your code here
}

Hint

Use println!("Minimum value in BST: {}", min_value); to print the result.

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