BST Find Minimum Element in DSA Rust

Mental Model

In a binary search tree, the smallest value is always found by going left until no more left child exists.

Analogy: Imagine a family tree where the oldest ancestor is always on the far left branch; to find the oldest, you keep moving left until you can't go further.

      10
     /  \
    5    15
   / \     
  2   7    
 /
1
↑

Dry Run Walkthrough

Input: BST with nodes 10, 5, 15, 2, 7, 1; find minimum element

Goal: Find the smallest value in the BST by moving left until no left child

Step 1: Start at root node 10

10 -> left: 5 -> right: 15

Why: We begin at the root to find the minimum

Step 2: Move left to node 5

10 -> [curr->5] -> right: 15

Why: Smaller values are on the left side

Step 3: Move left to node 2

10 -> 5 -> [curr->2]

Why: Keep moving left to find smaller values

Step 4: Move left to node 1

10 -> 5 -> 2 -> [curr->1]

Why: Continue left until no more left child

Step 5: No left child at node 1, stop

10 -> 5 -> 2 -> 1 [curr], left=null

Why: Node 1 is the smallest element

Result:

1 is the minimum element in the BST

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn find_min(root: Option<Rc<RefCell<TreeNode>>>) -> Option<i32> {
    let mut current = root;
    // advance current left until no left child
    while let Some(node) = current.clone() {
        if node.borrow().left.is_some() {
            current = node.borrow().left.clone();
        } else {
            return Some(node.borrow().val);
        }
    }
    None
}

fn main() {
    // Build the BST
    let root = TreeNode::new(10);
    let node5 = TreeNode::new(5);
    let node15 = TreeNode::new(15);
    let node2 = TreeNode::new(2);
    let node7 = TreeNode::new(7);
    let node1 = TreeNode::new(1);

    root.borrow_mut().left = Some(node5.clone());
    root.borrow_mut().right = Some(node15);
    node5.borrow_mut().left = Some(node2.clone());
    node5.borrow_mut().right = Some(node7);
    node2.borrow_mut().left = Some(node1);

    let min_val = find_min(Some(root));
    match min_val {
        Some(val) => println!("Minimum element in BST is {}", val),
        None => println!("BST is empty"),
    }
}

while let Some(node) = current.clone() {

loop to traverse down the left children

if node.borrow().left.is_some() {

check if left child exists to continue moving left

current = node.borrow().left.clone();

advance current pointer to left child

return Some(node.borrow().val);

return value when no left child found (minimum)

Output

Minimum element in BST is 1

Complexity Analysis

Time: O(h) because we traverse only the height of the tree down the left side

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Compared to searching all nodes, this is faster since minimum is always leftmost, avoiding full traversal

Edge Cases

Empty BST (root is None)

Returns None indicating no minimum element

DSA Rust

while let Some(node) = current.clone() {

BST with single node

Returns the single node's value as minimum

DSA Rust

if node.borrow().left.is_some() {

When to Use This Pattern

When asked to find the smallest element in a BST, look for the leftmost node because BST property guarantees smaller values are on the left.

Common Mistakes

Mistake: Trying to check right child or traversing entire tree to find minimum
Fix: Only traverse left children until no left child exists

Summary

Finds the smallest value in a BST by moving left until no left child.

Use when you need the minimum element quickly in a BST.

The smallest element is always the leftmost node in the BST.

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