Table of Contents
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
- 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// 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
Code for iteration will be :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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; } } |
|
1 2 3 4 |
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:
- Binary tree in java
- Binary tree preorder traversal
- Binary tree postorder traversal
- Binary tree inorder traversal
- Binary tree level order traversal
- Binary tree spiral order traversal
- Binary tree reverse level order traversal
- Binary tree boundary traversal
- Print leaf nodes of binary tree
- Count leaf nodes in binary tree
- get maximum element in binary tree
- Print all paths from root to leaf in binary tree
- Print vertical sum of binary tree in java
- Get level of node in binary tree in java
- Lowest common ancestor(LCA) in binary tree in java
Please go through java interview programs for more such programs.
