BST Find Minimum Element in DSA C - Execution Trace

Concept Flow - BST Find Minimum Element

Start at root

↓

Check if left child exists?

No→Current node is minimum

Yes↓

Move to left child

↩Back to check left child

Start at the root node and keep moving left until no left child exists. The current node then holds the minimum value.

Execution Sample

DSA C

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

int findMin(struct Node* root) {
    struct Node* current = root;
    while (current->left != NULL) {
        current = current->left;
    }
    return current->data;
}

This code finds the minimum element in a BST by moving left from the root until no left child exists.

Execution Table

Step	Operation	Current Node Data	Pointer Changes	Visual State
1	Start at root	15	current = root (15)	15 / \ 10 20
2	Check left child	15	current->left exists (10)	15 / \ 10 20
3	Move to left child	10	current = current->left (10)	15 / \ 10 20
4	Check left child	10	current->left exists (8)	15 / \ 10 20 / 8
5	Move to left child	8	current = current->left (8)	15 / \ 10 20 / 8
6	Check left child	8	current->left is NULL	15 / \ 10 20 / 8
7	Return minimum	8	No pointer change	15 / \ 10 20 / 8

💡 Left child is NULL at node 8, so 8 is the minimum element.

Variable Tracker

Variable	Start	After Step 3	After Step 5	Final
current	15 (root)	10 (left child of 15)	8 (left child of 10)	8 (minimum node)

Key Moments - 3 Insights

Why do we keep moving left to find the minimum?

In a BST, smaller values are always in the left subtree. So moving left leads to the smallest value. See execution_table steps 2, 4, and 6.

What if the root has no left child?

If root has no left child, root itself is the minimum. This is shown in execution_table step 6 where current->left is NULL.

Why do we stop when current->left is NULL, not current itself?

Because the minimum is the leftmost node, which has no left child. Stopping at current->left == NULL means current is the minimum node. See execution_table step 6.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 5?

A 15

B 10

C 8

D 20

💡 Hint

Check the 'Pointer Changes' and 'Current Node Data' columns at step 5.

At which step does the algorithm find that the left child is NULL?

A Step 4

B Step 6

C Step 3

D Step 7

💡 Hint

Look for the step where 'current->left is NULL' in the 'Pointer Changes' column.

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

A The root node's data

B The right child's data

C NULL

D The left child's data

💡 Hint

Refer to the key moment about root with no left child and execution_table step 6.

Concept Snapshot

BST Find Minimum Element:
- Start at root node
- Move left child repeatedly
- Stop when left child is NULL
- Current node is minimum
- Returns minimum value
- Works because BST left subtree has smaller values

Full Transcript

To find the minimum element in a Binary Search Tree (BST), start at the root node. Keep moving to the left child node as long as it exists. When you reach a node with no left child, that node contains the minimum value. This works because in BSTs, left children always hold smaller values than their parents. The code uses a pointer 'current' starting at root and moves left until current->left is NULL. Then it returns current->data as the minimum. If the root has no left child, the root itself is the minimum. This step-by-step process ensures the smallest element is found efficiently.

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 parent nodes.

2. Step 2: Locate minimum element

   Because smaller values go left, the minimum is at the leftmost node.

3. Final Answer:

   At the leftmost node -> Option A

4. Quick Check:

   Minimum element = leftmost node [OK]

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

Common Mistakes:

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

2. Which of the following C code snippets correctly finds the minimum element in a BST?

easy

A. while(root->left != NULL) root = root->right; return root->data;

B. while(root->left != NULL) root = root->left; return root->data;

C. if(root == NULL) return INT_MAX; return root->data;

D. while(root->right != NULL) root = root->right; return root->data;

Solution

1. Step 1: Check loop condition for minimum

   Minimum is found by moving left while left child exists.

2. Step 2: Verify code correctness

   while(root->left != NULL) root = root->left; return root->data; moves left until no left child, then returns data correctly.

3. Final Answer:

   while(root->left != NULL) root = root->left; return root->data; -> Option B

4. Quick Check:

   Traverse left to find minimum [OK]

Hint: Traverse left child until NULL to find minimum [OK]

Common Mistakes:

• Traversing right child instead of left
• Returning root data without traversal
• Incorrect loop condition

3. What will be the output of the following C code snippet for a BST?

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

struct Node* findMin(struct Node* root) {
  while(root->left != NULL) {
    root = root->left;
  }
  return root;
}

// Assume BST is:
//       10
//      /  \
//     5    15
//    / 
//   2

int main() {
  struct Node n2 = {2, NULL, NULL};
  struct Node n5 = {5, &n2, NULL};
  struct Node n15 = {15, NULL, NULL};
  struct Node n10 = {10, &n5, &n15};
  struct Node* minNode = findMin(&n10);
  printf("%d", minNode->data);
  return 0;
}

medium

A. 10

B. 5

C. 2

D. 15

Solution

1. Step 1: Trace findMin function

   Function moves left from root 10 to 5, then to 2, stops as 2 has no left child.

2. Step 2: Identify returned node data

   Returned node is 2, so printf prints 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Leftmost node data = 2 [OK]

Hint: Output is leftmost node's data in BST [OK]

Common Mistakes:

• Confusing leftmost with root
• Assuming right child is minimum
• Not following pointer traversal

4. Identify the error in the following C function that tries to find the minimum element in a BST:

struct Node* findMin(struct Node* root) {
  while(root->left == NULL) {
    root = root->left;
  }
  return root;
}

medium

A. Loop condition should be root->left != NULL

B. Function should return root->right

C. Missing check for root == NULL before loop

D. Should use recursion instead of loop

Solution

1. Step 1: Analyze loop condition

   Loop runs while root->left == NULL, which means it stops if left child exists, so it never moves left.

2. Step 2: Correct loop condition

   It should run while root->left != NULL to move left until no left child.

3. Final Answer:

   Loop condition should be root->left != NULL -> Option A

4. Quick Check:

   Traverse left while left child exists [OK]

Hint: Loop must continue while left child exists [OK]

Common Mistakes:

• Using == NULL instead of != NULL in loop
• Ignoring NULL root check
• Confusing left and right pointers

5. Given a BST where some nodes have only right children, how would you modify the findMin function to safely find the minimum element without causing a runtime error if the tree is empty?

hard

A. Traverse right child instead of left child

B. Return root->data immediately without traversal

C. Use recursion without base case

D. Add a check at start: if(root == NULL) return NULL; then traverse left

Solution

1. Step 1: Handle empty tree case

   Check if root is NULL at start to avoid dereferencing NULL pointer.

2. Step 2: Traverse left children safely

   If root is not NULL, move left while left child exists to find minimum.

3. Final Answer:

   Add a check at start: if(root == NULL) return NULL; then traverse left -> Option D

4. Quick Check:

   Check NULL root before traversal [OK]

Hint: Always check for NULL root before traversal [OK]

Common Mistakes:

• Not checking for empty tree causing crash
• Traversing right child for minimum
• Missing base case in recursion