BST Find Minimum Element in DSA C - 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 this tree. This is like finding the smallest book in a shelf arranged by size.

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

📋 What You'll Learn

Create a BST node structure with integer data and left/right pointers

Insert nodes with exact values 15, 10, 20, 8, 12 in the BST

Write a function findMin that returns the minimum value in the BST

Print the minimum value found by findMin

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to quickly find minimum or maximum values, like finding the earliest date or smallest ID.

💼 Career

Understanding BST operations is important for software engineers working on search algorithms, data indexing, and efficient data retrieval.

1

Create BST Node Structure and Insert Nodes

Create a struct called Node with an int data and two pointers left and right to Node. Then create a function newNode that takes an int data and returns a pointer to a new node with data set and left and right set to NULL. Finally, create a function insert that inserts a new node with given data into the BST following BST rules. In main, create a BST by inserting nodes with values 15, 10, 20, 8, and 12 in that order.

DSA C

#include 
#include 

// Define Node struct and newNode function
// Define insert function

int main() {
    // Insert nodes 15, 10, 20, 8, 12 into BST
    // Your code here
    return 0;
}

Hint

Start by defining the Node structure and functions to create and insert nodes. Then insert the given values into the BST in main.

2

Create a Function to Find Minimum Node

Create a function called findMin that takes a pointer to Node called root and returns a pointer to the node with the smallest data in the BST. Remember, in a BST, the minimum value is found by going as far left as possible.

DSA C

#include 
#include 

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

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

Node* insert(Node* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }
    if (data data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

// Define findMin function here

int main() {
    Node* root = NULL;
    root = insert(root, 15);
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 8);
    root = insert(root, 12);
    // Your code here
    return 0;
}

Hint

Use a loop to move left from the root until you reach a node with no left child. Return that node.

3

Call findMin and Store Result

In main, call findMin with the root of the BST and store the returned pointer in a variable called minNode.

DSA C

#include 
#include 

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

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

Node* insert(Node* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }
    if (data data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

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

int main() {
    Node* root = NULL;
    root = insert(root, 15);
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 8);
    root = insert(root, 12);
    // Call findMin and store result in minNode
    // Your code here
    return 0;
}

Hint

Use Node* minNode = findMin(root); to store the minimum node pointer.

4

Print the Minimum Element

Add a printf statement in main to print the minimum element's data from minNode in the format: Minimum element is: X\n where X is the minimum value.

DSA C

#include 
#include 

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

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

Node* insert(Node* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }
    if (data data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

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

int main() {
    Node* root = NULL;
    root = insert(root, 15);
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 8);
    root = insert(root, 12);
    Node* minNode = findMin(root);
    // Print the minimum element
    // Your code here
    return 0;
}

Hint

Use printf("Minimum element is: %d\n", minNode->data); to print the minimum value.

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