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)

Method 2 :- Find the maximum element in a binary tree without using recursion.