BST Find Minimum Element in DSA Rust - Execution Trace

Concept Flow - BST Find Minimum Element

Start at root node

↓

Check if left child exists?

No→Current node is minimum

Yes↓

Move to left child

↩Back to check left child

Start from the root and keep moving left until no left child exists; that node holds the minimum value.

Execution Sample

DSA Rust

fn find_min(root: &Option<Box<Node>>) -> Option<i32> {
    let mut current = root;
    while let Some(node) = current {
        if node.left.is_none() {
            return Some(node.value);
        }
        current = &node.left;
    }
    None
}

This function finds the minimum value in a BST by traversing left children until none remain.

Execution Table

Step	Operation	Current Node Value	Left Child Exists?	Pointer Changes	Visual State
1	Start at root	10	Yes	current -> Node(10)	10 / \ 5 15
2	Check left child	10	Yes	Move current to left child	10 / \ 5 15
3	At node 5	5	Yes	current -> Node(5)	10 / \ 5 15 / 2
4	Check left child	5	Yes	Move current to left child	10 / \ 5 15 / 2
5	At node 2	2	No	current -> Node(2)	10 / \ 5 15 / 2
6	No left child	2	No	Return 2 as minimum	10 / \ 5 15 / 2
7	End	-	-	-	Minimum found: 2

💡 Traversal stops when current node has no left child; that node's value is minimum.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	Final
current	Node(10)	Node(5)	Node(2)	Node(2)	Node(2)

Key Moments - 3 Insights

Why do we keep moving left instead of right?

Because in a BST, smaller values are always in the left subtree. The execution_table rows 2, 4 show moving left to find smaller values.

What if the tree is empty (root is None)?

The function returns None immediately since current is None at start, meaning no nodes exist. This is implied before step 1 in execution_table.

Why do we return the current node's value when left child is None?

Because no smaller value exists to the left, so current node holds the minimum. See step 6 in execution_table where left child is None and value 2 is returned.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node value at step 4?

A 10

B 5

C 2

D 15

💡 Hint

Check the 'Current Node Value' column at step 4 in execution_table.

At which step does the traversal stop because there is no left child?

A Step 6

B Step 5

C Step 3

D Step 7

💡 Hint

Look for the step where 'Left Child Exists?' is 'No' and the minimum is returned.

If the root node had no left child, what would be the minimum value returned?

A None

B Value of right child

C Value of root node

D Value of leftmost leaf

💡 Hint

Refer to the concept_flow and execution_table step 1 and 6 where no left child means current node is minimum.

Concept Snapshot

BST Find Minimum Element:
- Start at root node
- While left child exists, move left
- When no left child, current node is minimum
- Return current node's value
- If tree empty, return None

Full Transcript

To find the minimum element in a Binary Search Tree (BST), start at the root node. Check if the current node has a left child. If yes, move to that left child and repeat. If no left child exists, the current node holds the minimum value. Return this value. If the tree is empty, return None. This process works because in BSTs, smaller values are always in the left subtree. The code uses a loop to traverse left until no left child is found, then returns the current node's value as minimum.

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