Home Trees Find the maximum element in a binary tree

# Find the maximum element in a binary tree

Question: Given the root pointer to a binary tree, find the maximum element present in it.

Input: Sample Tree (Pointer to node 1 is given)
Output: Maximum = 9

One simple way of solving this problem is to find the maximum element in the left sub-tree, find maximum in the right sub-tree, compare it with the root data and select the one that gives the maximum value. This approach can be easily implemented with recursion.

This approach works because each node of the tree has 3 parts -> the root, the left and the right.
What we do is we get the maximum of these 3 values.

If we break into parts:-

• From the left sub-tree we have root = 2, left = 7 and right = 9. Therefore MAX = 9 (in left sub-tree)
• From the right sub-tree we have root = 3, left = 5 and right = 4. Therefore MAX = 5 (in right sub-tree)
• Coming to the root node we have root = 1, left = 9 and right = 5. Therefore MAX = 9 (complete tree)

Each node is a tree within itself and thus, we apply this property recursively to each of the nodes.

#include<stdio.h>
#define MIN -65535

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

int findMaxInTree(struct binaryTreeNode * root)
{
// A variable for root value
int root_val;

// Variable to store values in left and right tree
int left, right;

// Initialize it with a minimum value
int max = MIN;

if(root != NULL)
{
// Get the root value
root_val = root -> data;

// Find the maximum value in left sub-tree
left = findMaxInTree(root -> left);

// Find the maximum value in right sub-tree
right = findMaxInTree(root -> right);

// Now find the largest of 3 values
// Find which is big among left and right
if(left > right)
max = left;
else
max = right;

// Compare the max with root value
if(root_val > max)
max = root_val;
}

return max;
}


Time Complexity:- O(n)
Space Complexity:- O(n)

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More