Given a binary tree, find the maximum element in it. In this tutorial, we are going to write a code to find the maximum element in a binary tree without using recursion.
For example:
In this binary tree, the maximum element is 9.
How do we solve this problem? How we can find the max element in a binary tree? Do we need to visit each node to find the max element?
In a binary tree, we need to visit each node to find the greatest element present in it. So, the idea here is to visit each node to find the maximum element in it.
In this tutorial, I am going to discuss the iterative approach to solve this problem. If you don’t know the difference between recursive and iterative approach. Then, check my previous tutorial in which I have explained recursion vs iteration.
Find Maximum Element in Binary Tree without using Recursion – Java Code
In this example, we are going to use the iterative approach to find the maximum element. For this, we are going to use binary tree level order traversal.
The idea here is to visit each node level by level so that we can keep track of the max element present in a binary tree.
Here are the following steps:
i) Declare a max variable and assign an integer min value.
ii) Declare a queue and add a root node in a queue.
iii) Run a while loop while the queue is not empty and perform the following steps
a) poll a queue and compare the node data with the variable max.
b) Enqueue left and right children of a node if it’s not null.
iv) Once the traversal is complete we get the maximum element.
|
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 |
//Find max using iterative approach public class MaximumElement { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; } } public static int findMaxIteratively(TreeNode node) { //Assign integer min value (-2147483648) int max = Integer.MIN_VALUE; //Declare a queue Queue<TreeNode> queue = new LinkedList<>(); queue.add(node); //Add root node //While queue is not empty while (!queue.isEmpty()) { //Retrieve and remove the head of the queue TreeNode nodeData = queue.poll(); //Compare the node data with max if(nodeData.data > max) { max = nodeData.data; } //If left child is not null if (nodeData.left != null) { queue.add(nodeData.left); } //If right child is not null if (nodeData.right != null) { queue.add(nodeData.right); } } return max; } public static TreeNode createBinaryTree() { TreeNode rootNode = new TreeNode(7); rootNode.left = new TreeNode(6); rootNode.right = new TreeNode(5); rootNode.left.left = new TreeNode(4); rootNode.left.right = new TreeNode(3); rootNode.left.right.right = new TreeNode(9); rootNode.right.left = new TreeNode(2); rootNode.right.right = new TreeNode(1); return rootNode; } public static void main(String[] args) { int max = findMaxIteratively(createBinaryTree()); System.out.println(" Maximum element of a binary tree " + max); } } |
Find the Max Element in Binary Tree without using Recursion | Video Tutorial
