Find maximum/ largest element in a binary tree ( java/ BFS / example)

• Given a binary tree, find out the maximum or largest element using non recursive algorithm.
• Traverse the binary tree using depth first search (DFS) or level order traversal.

Example:  Maximum element in a binary tree using java

• Create max variable to denote largest element in a binary tree.
• Visit the Level 0 and maximum value will be set to 50[Refer Fig 1]
• Go to Level 1 & visit all nodes
  • Visit Node 25, which is less than current max value 50
    • max value will not be updated
  • Visit Next node 30, which is less the current max 50
    • max value will not be updated
• Go to Level 2 & visit all nodes
  • Node D, Node E & Node F are less than current max value.
    • max value will not be updated
  • When we visited Node G.
    • max value is greater than current max, so max will be updated to 60.
• Maximum or largest element in a binary tree is 60.
• Visited all nodes [Refer Fig 2]

Time complexity of algorithm is O(n).

Program: Maximum or largest element – binary tree

1.) MaxElement Class:

• MaxElement class is responsible for finding the maximum or largest element in a binary tree.
• Traverse the binary tree using level order traversal or breadth first search (non recursive) algorithm.

package org.learn.Question;

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

public class MaxElement {
 public static int maxElement(Node root) {
  if (root == null) {
   System.out.println("Tree is empty");
   return Integer.MIN_VALUE;
  }
  int max = root.data;
  Queue<Node> queue = new LinkedList<Node>();
  queue.offer(root);

  while (!queue.isEmpty()) {
   Node node = queue.poll();
   if(max < node.data) {
    max = node.data;
   }
   if (node.left != null) {
    queue.offer(node.left);
   }
   if (node.right != null) {
    queue.offer(node.right);
   }
  }
  System.out.println("Max Element in Binary Tree is : " + max);
  return max;
 }
}

2.) Node Class:

• Node class is representing the node(s) of a binary tree.

package org.learn.Question;

public class Node {
 public int data;
 public Node left;
 public Node right;

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }
 
 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class:

• We are creating a binary tree in main method.
• We are calling method of maxElement class to find maximum element in a binary tree

package org.learn.Client;

import org.learn.Question.MaxElement;
import org.learn.Question.Node;

public class App {
 public static void main(String[] args) {
  // root level 0
  Node A = Node.createNode(50);
  // Level 1
  Node B = Node.createNode(25);
  Node C = Node.createNode(30);
  // Level 2
  Node D = Node.createNode(40);
  Node E = Node.createNode(10);
  Node F = Node.createNode(30);
  Node G = Node.createNode(60);
  
  // connect Level 0 and 1
  A.left = B;
  A.right = C;
  // connect level 1 and level 2
  B.left = D;
  B.right = E;
  C.left = F;
  C.right = G;
  // connect level 2 and level 3
  MaxElement.maxElement(A);
 }
}

Output : maximum or largest element in binary tree (Java/BFS)

Max Element in Binary Tree is : 60

Code: maximum element binary tree non recursive (BFS)