Find Maximum Element in Binary Tree in Java

Table of Contents [hide]

1. Overview
2. Introduction to Problem Statement
3. Implementation
- 3.1 Recursive
- 3.2 Iterative
4. Complete Java Program
5. Conclusion

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

1. Overview

In this article, we will explore how to find the maximum element in a binary tree in Java using recursive and iterative solutions.

2. Introduction to Problem Statement

Given a binary tree as below:

Maximum element in binary tree is: 70
Our goal is to find an efficient method to traverse the tree and find this maximum value.

3. Implementation

There can be two solutions for it:

Recursive
Iterative

3.1 Recursive

Steps for getting maximum element in binary tree:

Find maximum element in left subtree.
Find maximum element in right subtree.
Compare maximum of above subtrees to current node.
We will find maximum element with the above steps.

Code for recursion will be:

  // Recursive Solution
 /* To get max node in a binary tree*/
 // Recursive Solution
    /* To get the max node in a binary tree*/
    public static  int getMaximumRec(TreeNode root)
    {
        int max=Integer.MIN_VALUE;
        int value=0;
        int left,right;
        if(root != null)
        {
            value=root.data;
            left=getMaximumRec(root.left);
            right=getMaximumRec(root.right);

            if(left>right)
            {
                max=left;
            }
            else
            {
                max=right;
            }

            if(max < value)
            {
                max=value;
            }
        }

        return max;
    }

// Recursive Solution

/* To get max node in a binary tree*/

// Recursive Solution

/* To get the max node in a binary tree*/

public static int getMaximumRec(TreeNode root)

{

int max=Integer.MIN_VALUE;

int value=0;

int left,right;

if(root != null)

{

value=root.data;

left=getMaximumRec(root.left);

right=getMaximumRec(root.right);

if(left>right)

{

max=left;

}

else

{

max=right;

}

if(max < value)

{

max=value;

}

return max;

}

Time Complexity: O(n), where n is the number of nodes, as it visits each node exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

3.2 Iterative

Iterative solution will be similar to level order traversal. When we are popping an element from queue, we will check max.

Code for iteration will be :

        // Iterative Solution
    /* To get max node in a binary tree*/
    public static int getMaximumItr(TreeNode startNode) {

        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(startNode);
        int max=Integer.MIN_VALUE;
        while(!queue.isEmpty())
        {
            TreeNode tempNode=queue.poll();
            if(max < tempNode.data)
                max=tempNode.data;
            if(tempNode.left!=null)
                queue.add(tempNode.left);
            if(tempNode.right!=null)
                queue.add(tempNode.right);
        }
        return max;
    }

// Iterative Solution

/* To get max node in a binary tree*/

public static int getMaximumItr(TreeNode startNode) {

Queue<TreeNode> queue=new LinkedList<>();

queue.add(startNode);

int max=Integer.MIN_VALUE;

while(!queue.isEmpty())

{

TreeNode tempNode=queue.poll();

if(max < tempNode.data)

max=tempNode.data;

if(tempNode.left!=null)

queue.add(tempNode.left);

if(tempNode.right!=null)

queue.add(tempNode.right);

}

return max;

}

Time Complexity: O(n), similar to the recursive solution.
Space Complexity: O(h), but since it’s iterative, it avoids the potential stack overflow issue.

4. Complete Java Program

Let’s say our binary tree is:

Here is a complete Java program to find the max element in binary tree:

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeGetMaxElement {
    /*
     * @Author : Arpit Mandliya
     */

    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    // Recursive Solution
    /* To get the max node in a binary tree*/
    public static  int getMaximumRec(TreeNode root)
    {
        int max=Integer.MIN_VALUE;
        int value=0;
        int left,right;
        if(root != null)
        {
            value=root.data;
            left=getMaximumRec(root.left);
            right=getMaximumRec(root.right);

            if(left>right)
            {
                max=left;
            }
            else
            {
                max=right;
            }

            if(max < value)
            {
                max=value;
            }
        }

        return max;
    }

    // Iterative Solution
    /* To get max node in a binary tree*/
    public static int getMaximumItr(TreeNode startNode) {

        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(startNode);
        int max=Integer.MIN_VALUE;
        while(!queue.isEmpty())
        {
            TreeNode tempNode=queue.poll();
            if(max < tempNode.data)
                max=tempNode.data;
            if(tempNode.left!=null)
                queue.add(tempNode.left);
            if(tempNode.right!=null)
                queue.add(tempNode.right);
        }
        return max;
    }

    public static void main(String[] args)
    {
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Max node using recursion :"+getMaximumRec(rootNode));
        System.out.println("Max node using iteration :"+getMaximumItr(rootNode));
    }

    public static TreeNode createBinaryTree()
    {

        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);

        rootNode.left=node20;
        rootNode.right=node60;

        node20.left=node10;
        node20.right=node30;

        node60.left=node50;
        node60.right=node70;

        return rootNode;
    }
}

100

101

102

103

import java.util.LinkedList;

import java.util.Queue;

public class BinaryTreeGetMaxElement {

* @Author : Arpit Mandliya

public static class TreeNode

{

int data;

TreeNode left;

TreeNode right;

TreeNode(int data)

{

this.data=data;

}

// Recursive Solution

/* To get the max node in a binary tree*/

public static int getMaximumRec(TreeNode root)

{

int max=Integer.MIN_VALUE;

int value=0;

int left,right;

if(root != null)

{

value=root.data;

left=getMaximumRec(root.left);

right=getMaximumRec(root.right);

if(left>right)

{

max=left;

}

else

{

max=right;

}

if(max < value)

{

max=value;

}

return max;

}

// Iterative Solution

/* To get max node in a binary tree*/

public static int getMaximumItr(TreeNode startNode) {

Queue<TreeNode> queue=new LinkedList<>();

queue.add(startNode);

int max=Integer.MIN_VALUE;

while(!queue.isEmpty())

{

TreeNode tempNode=queue.poll();

if(max < tempNode.data)

max=tempNode.data;

if(tempNode.left!=null)

queue.add(tempNode.left);

if(tempNode.right!=null)

queue.add(tempNode.right);

}

return max;

}

public static void main(String[] args)

{

// Creating a binary tree

TreeNode rootNode=createBinaryTree();

System.out.println("Max node using recursion :"+getMaximumRec(rootNode));

System.out.println("Max node using iteration :"+getMaximumItr(rootNode));

}

public static TreeNode createBinaryTree()

{

TreeNode rootNode =new TreeNode(40);

TreeNode node20=new TreeNode(20);

TreeNode node10=new TreeNode(10);

TreeNode node30=new TreeNode(30);

TreeNode node60=new TreeNode(60);

TreeNode node50=new TreeNode(50);

TreeNode node70=new TreeNode(70);

rootNode.left=node20;

rootNode.right=node60;

node20.left=node10;

node20.right=node30;

node60.left=node50;

node60.right=node70;

return rootNode;

}

Run the above program, and you will get the following output:

Max node using recursion :70
Max node using iteration :70

Max node using recursion :70

Max node using iteration :70

5. Conclusion

In this article, we covered about how to find maximum element in binary tree. We have done traversal using two approaches: Iterative and Recursive. We also discussed about time and space complexity for the solutions.
Java Binary tree tutorial:

Please go through java interview programs for more such programs.

Was this post helpful?

Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.

Find Maximum Element in Binary Tree in Java

1. Overview

2. Introduction to Problem Statement

3. Implementation

3.1 Recursive

3.2 Iterative

4. Complete Java Program

5. Conclusion

Was this post helpful?

Author

Leave a Reply Cancel reply

Categories

Popular Posts

Let’s be Friends

1. Overview

2. Introduction to Problem Statement

3. Implementation

3.1 Recursive

3.2 Iterative

4. Complete Java Program

5. Conclusion

Was this post helpful?

Related posts:

Share this

Author

Leave a Reply Cancel reply

Let’s be Friends