*2K*

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.