C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree — Finding Minimum and Maximum Element in a BST

This is an essential operation used in searching, deletion, range queries, and successor/predecessor algorithms.

Binary Search Tree — Find Minimum and Maximum Elements

Concept Overview

In a BST:

  • The left child of a node contains values smaller than the parent.
  • The right child contains values greater than the parent.

Hence:

  • The minimum element is the leftmost node in the tree.
  • The maximum element is the rightmost node in the tree.

Logic Summary

To find the minimum:

struct Node* findMin(struct Node* root) {

    while (root && root->left != NULL)

        root = root->left;

    return root;

}

To find the maximum:

struct Node* findMax(struct Node* root) {

    while (root && root->right != NULL)

        root = root->right;

    return root;

}

Both operations traverse only one side of the tree — making them O(h), where h is the height.

 

C Program: Binary Search Tree - Finding Minimum and Maximum Element in a BST

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure for BST Node


struct Node {


    int data;


    struct Node *left, *right;


};


 


// Function to create a new node


struct Node* createNode(int value) {


    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));


    newNode->data = value;


    newNode->left = newNode->right = NULL;


    return newNode;


}


 


// Function to insert a node in BST


struct Node* insert(struct Node* root, int value) {


    if (root == NULL)


        return createNode(value);


 


    if (value < root->data)


        root->left = insert(root->left, value);


    else if (value > root->data)


        root->right = insert(root->right, value);


 


    return root;


}


 


// Function to find minimum element


struct Node* findMin(struct Node* root) {


    if (root == NULL)


        return NULL;


    while (root->left != NULL)


        root = root->left;


    return root;


}


 


// Function to find maximum element


struct Node* findMax(struct Node* root) {


    if (root == NULL)


        return NULL;


    while (root->right != NULL)


        root = root->right;


    return root;


}


 


// Inorder traversal for verification


void inorder(struct Node* root) {


    if (root != NULL) {


        inorder(root->left);


        printf("%d ", root->data);


        inorder(root->right);


    }


}


 


int main() {


    struct Node* root = NULL;


 


    // Construct BST


    root = insert(root, 50);


    root = insert(root, 30);


    root = insert(root, 70);


    root = insert(root, 20);


    root = insert(root, 40);


    root = insert(root, 60);


    root = insert(root, 80);


 


    printf("Inorder Traversal of BST: ");


    inorder(root);


    printf("\n");


 


    struct Node* minNode = findMin(root);


    struct Node* maxNode = findMax(root);


 


    if (minNode)


        printf("Minimum Element in BST: %d\n", minNode->data);


    if (maxNode)


        printf("Maximum Element in BST: %d\n", maxNode->data);


 


    return 0;


}

Output

 
OUTPUT :
Inorder Traversal of BST: 20 30 40 50 60 70 80
Minimum Element in BST: 20
Maximum Element in BST: 80

Visualization

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

  • Leftmost Node → 20 → Minimum
  • Rightmost Node → 80 → Maximum

Complexity Analysis

Operation

Time Complexity

Space Complexity

Find Minimum

O(h)

O(1)

Find Maximum

O(h)

O(1)

For a balanced BST, h = log₂(n)
For a skewed BST, h = n

Key Points

  • The minimum value is found by going left until NULL.
  • The maximum value is found by going right until NULL.
  • These operations are fast and form the base for:
    • Finding successors/predecessors
    • Deletion logic in BSTs
    • Range-based queries

 

Previous
Next