Program to Find Maximum Node of Binary Tree

• Write a program in C to find maximum node of binary tree.
• Write a recursive function to find maximum element of tree.

Given a binary tree of integers, we have to find the maximum 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 maximum value node. Here we will use recursion to find maximum node of a tree because this problem can be broken down to sub problems of finding maximum nodes in sub trees.

Here is the recursive equation
getMaximum(root) = Maximum of(getMaximum(root->left), getMaximum(root->right), root).

---

Algorithm to find maximum 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 maximum value node in left and right sub tree. Let it be "leftMax" and "rightMax".
• Return maximum of leftMax, rightMax 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 "getMaximumNode" which returns the maximum node of a binary tree by implementing above mentioned algorithm.

/* Returns maximum value node of binary tree */
int getMaximumNode(struct node *root){
 int leftMax= INT_MIN, rightMax=INT_MIN;
 /* Leaf node */
 if(root->left == NULL && root->right == NULL)
     return root->data;
 /* Recursively find the maximum value 
 in left and right subtree */
 if(root->left)
     leftMax = getMaximumNode(root->left);
 if(root->right)
     rightMax = getMaximumNode(root->right);
 /* returns maximum of root, left Subtree max node 
 and right Sub tree max node */
 return getMax(getMax(leftMax, rightMax), 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
            1
           / \
         9    12
        / \    \
       4  50    -7
      / \
     18  9
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
    // 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(-7);
    // Level 4 nodes
    root->left->left->left = getNewNode(18);
    root->left->left->right = getNewNode(9);
    
    return root;

}

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

/* Returns maximum value node of binary tree */
int getMaximumNode(struct node *root){
 int leftMax= INT_MIN, rightMax=INT_MIN;
 /* Leaf node */
 if(root->left == NULL && root->right == NULL)
     return root->data;
 /* Recursively find the maximum value 
 in left and right subtree */
 if(root->left)
     leftMax = getMaximumNode(root->left);
 if(root->right)
     rightMax = getMaximumNode(root->right);
 /* returns maximum of root, left Subtree max node 
 and right Sub tree max node */
 return getMax(getMax(leftMax, rightMax), root->data);
}

int main() {
    struct node *root = generateBTree();    
    
    /*Printing maximum node of tree  */
    printf("Maximum Node : %d", getMaximumNode(root));
    
    getchar();
    return 0; 
}

Output

Maximum Node : 50