BST Find Minimum Element in DSA C

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 tree where smaller numbers are always on the left side. To find the smallest number, you keep walking left until you can't go further.

      5
     / \
    3   8
   / \   
  1   4  
 ↑
(root)

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 8 -> 1 -> 4, find minimum element

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

Step 1: Start at root node with value 5

5 -> 3 -> 8 -> 1 -> 4, current = 5 ↑

Why: We begin search from the root to find minimum

Step 2: Move current pointer to left child 3

5 -> [curr->3] -> 8 -> 1 -> 4

Why: Smaller values are on the left, so move left

Step 3: Move current pointer to left child 1

5 -> 3 -> [curr->1] -> 4 -> 8

Why: Continue moving left to find smaller value

Step 4: No left child of current node 1, stop

5 -> 3 -> 1 ↑ -> 4 -> 8

Why: Reached leftmost node, which is minimum

Result:

1 -> null (minimum element found)

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define node structure
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Insert node in BST
Node* insert(Node* root, int data) {
    if (root == NULL) return newNode(data);
    if (data < root->data) root->left = insert(root->left, data);
    else root->right = insert(root->right, data);
    return root;
}

// Find minimum element in BST
int findMin(Node* root) {
    if (root == NULL) {
        printf("Tree is empty\n");
        return -1;
    }
    Node* current = root;
    while (current->left != NULL) {
        current = current->left; // move left to find smaller value
    }
    return current->data; // leftmost node data is minimum
}

int main() {
    Node* root = NULL;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 8);
    root = insert(root, 1);
    root = insert(root, 4);

    int minVal = findMin(root);
    printf("Minimum element in BST: %d\n", minVal);
    return 0;
}

while (current->left != NULL) {

advance current to left child to find smaller value

current = current->left;

move current pointer left until no left child

return current->data;

return data of leftmost node as minimum

Output

Minimum element in BST: 1

Complexity Analysis

Time: O(h) because we traverse down the height of the tree following left children

Space: O(n) due to recursive insert calls; findMin uses O(1) extra space

vs Alternative: Compared to scanning all nodes (O(n)), this method is faster as it only goes left down the tree height

Edge Cases

Empty tree

Function prints 'Tree is empty' and returns -1

DSA C

if (root == NULL) {

Tree with single node

Returns the root node's value as minimum

DSA C

while (current->left != NULL) {

When to Use This Pattern

When asked to find the smallest element in a BST, look for the leftmost node by following left pointers until none remain.

Common Mistakes

Mistake: Trying to find minimum by checking all nodes instead of just going left
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 exists.

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 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