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.