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 family tree where the youngest child is always the leftmost branch; to find the youngest, you keep moving left until you can't go further.

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

Dry Run Walkthrough

Input: BST: 10 -> 5 -> 15 -> 2 -> 7 -> 1, find minimum element

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

Step 1: Start at root node with value 10

10 -> 5 -> 15 -> 2 -> 7 -> 1, current = 10 ↑

Why: We begin search from the root to find the minimum

Step 2: Move to left child of 10, which is 5

10 -> [current->5] -> 15 -> 2 -> 7 -> 1

Why: Minimum must be in left subtree, so go left

Step 3: Move to left child of 5, which is 2

10 -> 5 -> [current->2] -> 7 -> 1 -> 15

Why: Keep moving left to find smaller values

Step 4: Move to left child of 2, which is 1

10 -> 5 -> 2 -> [current->1] -> 7 -> 15

Why: Continue left until no more left child

Step 5: No left child of 1, stop here

10 -> 5 -> 2 -> 1 ↑ -> 7 -> 15

Why: Reached the smallest element in BST

Result:

Minimum element found: 1

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

int findMin(Node* root) {
    // Move left until no left child
    while (root && root->left) {
        root = root->left; // advance to left child
    }
    return root ? root->val : -1; // return value or -1 if empty
}

int main() {
    Node* root = nullptr;
    int values[] = {10, 5, 15, 2, 7, 1};
    for (int v : values) {
        root = insert(root, v);
    }
    int minVal = findMin(root);
    cout << "Minimum element found: " << minVal << endl;
    return 0;
}

while (root && root->left) {

advance root to left child to find smaller values

root = root->left;

move pointer left until no more left child

return root ? root->val : -1;

return smallest value found or -1 if tree empty

Output

Minimum element found: 1

Complexity Analysis

Time: O(h) where h is the height of the BST because we only traverse down the left edge

Space: O(1) because we use only a pointer to traverse without extra storage

vs Alternative: Compared to searching all nodes (O(n)), this is faster as it only follows left children

Edge Cases

Empty BST

Returns -1 indicating no minimum element

DSA C++

return root ? root->val : -1;

BST with only one node

Returns the value of the single node as minimum

DSA C++

while (root && root->left) {

When to Use This Pattern

When you need the smallest element in a BST, look for the leftmost node by moving left until no child exists.

Common Mistakes

Mistake: Trying to find minimum by checking all nodes instead of just left children
Fix: Only traverse left children until no left child remains

Mistake: Not handling empty tree and returning invalid value
Fix: Check if root is null and return a sentinel value like -1

Summary

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

Use when you want 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 any leaf node

B. At the leftmost node

C. At the root node

D. At the rightmost 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 B

4. Quick Check:

   Minimum = 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 of the following C++ code snippets correctly finds the minimum element in a BST node pointer root?

easy

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

B. while(root->right != nullptr) root = root->right; return root->data;

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

D. return root->data;

Solution

1. Step 1: Check traversal direction

   Minimum is found by moving left until no left child exists.

2. Step 2: Verify code correctness

   while(root->left != nullptr) root = root->left; return root->data; loops left correctly and returns the leftmost node's data.

3. Final Answer:

   while(root->left != nullptr) root = root->left; return root->data; -> Option A

4. Quick Check:

   Traverse left to find minimum [OK]

Hint: Loop left child until null to find minimum [OK]

Common Mistakes:

• Looping right child instead of left
• Returning root data without traversal
• Not checking for nullptr before access

3. What is the output of the following C++ code snippet?

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

Node* root = new Node{10, nullptr, nullptr};
root->left = new Node{5, nullptr, nullptr};
root->right = new Node{15, nullptr, nullptr};
root->left->left = new Node{2, nullptr, nullptr};

Node* temp = root;
while(temp->left != nullptr) {
  temp = temp->left;
}
std::cout << temp->data << std::endl;

medium

A. 10

B. 5

C. 2

D. 15

Solution

1. Step 1: Trace the tree structure

   Root is 10, left child 5, left-left child 2, right child 15.

2. Step 2: Follow the loop to find minimum

   Loop moves from 10 to 5, then to 2, which has no left child.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Leftmost node data = 2 [OK]

Hint: Follow left pointers until null to find minimum [OK]

Common Mistakes:

• Stopping at root or first left child
• Confusing right child as minimum
• Not tracing loop fully

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

int findMin(Node* root) {
  if(root == nullptr) return -1;
  while(root->right != nullptr) {
    root = root->right;
  }
  return root->data;
}

medium

A. Loops on right child instead of left child

B. Returns -1 when root is nullptr

C. Returns root->data without checking nullptr

D. Function return type should be Node*

Solution

1. Step 1: Analyze loop direction

   Minimum element is found by moving left, not right.

2. Step 2: Identify incorrect traversal

   The code loops on root->right, which finds maximum, not minimum.

3. Final Answer:

   Loops on right child instead of left child -> Option A

4. Quick Check:

   Minimum requires left traversal [OK]

Hint: Minimum is leftmost, not rightmost [OK]

Common Mistakes:

• Using right child loop for minimum
• Ignoring nullptr checks
• Confusing min and max logic

5. Given a BST where some nodes have only right children, how would you modify the standard minimum element search to handle this edge case correctly?

hard

A. Return root data immediately if left child is nullptr

B. Traverse right child until nullptr to find minimum

C. Use recursion to check both left and right children

D. Traverse left child until nullptr; if none, root is minimum

Solution

1. Step 1: Understand edge case

   If no left child exists, root itself is minimum.

2. Step 2: Modify search logic

   Traverse left until nullptr; if none found, root is minimum.

3. Final Answer:

   Traverse left child until nullptr; if none, root is minimum -> Option D

4. Quick Check:

   Minimum = leftmost or root if no left child [OK]

Hint: If no left child, root is minimum [OK]

Common Mistakes:

• Assuming minimum always has left child
• Traversing right child for minimum
• Not handling single-child nodes