Program to Find Minimum Node of Binary Tree

  • Write a C program to calculate minimum node of a binary tree.
  • Write a recursive function to find minimum value of tree.

Given a binary tree of integers, we have to find the minimum node of a binary tree. As there is no pre defined sequence of nodes in tree(unlike binary search tree), we have to traverse whole tree and check for minimum value node. Here we will use recursion to find minimum node of a tree because this problem can be broken down to sub problems of finding minimum nodes in sub trees.

Here is the recursive equation
getMinimum(root) = Minimum of(getMinimum(root->left), getMinimum(root->right), root).
Algorithm to find minimum node of a binary tree
Let "root" be the root node of given binary tree.
  • If root is a leaf node, then return root node's value.
  • Recursively find the minimum value node in left and right sub tree. Let it be "leftMin" and "rightMin".
  • Return maximum of leftMin, rightMin and root.
Time Complexity : O(n)
Space Complexity : O(1) without considering the internal stack space used for recursive calls, otherwise O(n).

In this program, we will use a user recursive function "getMinimumNode" which returns the minimum node of a binary tree by implementing above mentioned algorithm. 

int getMinimumNode(struct node *root){
    int leftMin= INT_MAX, rightMin=INT_MAX;
    /* Leaf node */
    if(root->left == NULL && root->right == NULL)
        return root->data;
    /* Recursively find the minimum value 
     in left and right subtree */
    if(root->left)
        leftMin = getMinimumNode(root->left);
    if(root->right)
        rightMin = getMinimumNode(root->right);
    /* returns minimum of root, left Subtree max node 
     and right Sub tree max node */
    return getMin(getMin(leftMin, rightMin), root->data);
}

C program to find maximum node of a binary tree

#include <stdio.h>
#include <limits.h>

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

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            7
           / \
         9    12
        / \    \
       4  50    8
      / \
     18  9
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(7);
    // Level 2 nodes 
    root->left = getNewNode(9);
    root->right = getNewNode(12);
    // Level 3 nodes
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(50);
    root->right->right = getNewNode(8);
    // Level 4 nodes
    root->left->left->left = getNewNode(18);
    root->left->left->right = getNewNode(9);
    
    return root;

}

/* Returns minimum of two number */
int getMin(int a, int b){
 if(a >= b)
     return b;
 return a;
}

/* Returns minimum value node of binary tree */
int getMinimumNode(struct node *root){
    int leftMin= INT_MAX, rightMin=INT_MAX;
    /* Leaf node */
    if(root->left == NULL && root->right == NULL)
        return root->data;
    /* Recursively find the minimum value 
     in left and right subtree */
    if(root->left)
        leftMin = getMinimumNode(root->left);
    if(root->right)
        rightMin = getMinimumNode(root->right);
    /* returns minimum of root, left Subtree max node 
     and right Sub tree max node */
    return getMin(getMin(leftMin, rightMin), root->data);
}

int main() {
    struct node *root = generateBTree();    
    
    /*Printing maximum node of tree  */
    printf("Minimum Node : %d", getMinimumNode(root));
    
    getchar();
    return 0; 
}
Output
Minimum Node : 4
Posted by
Labels: