Q:

Program to find the largest element in a Binary Tree

belongs to collection: Tree Programs

robaa
Save to bookmark
|
2022-11-09
|
  281 
0

Explanation

In this program, we will find out the largest node in the given binary tree. We first define variable max that will hold root's data. Then, we traverse through the left sub-tree to find the largest node. Compare it with max and store the maximum of two in a variable max. Then, we traverse through the right subtree to find the largest node and compare it with max. In the end, max will have the largest node.

Above diagram represents a binary tree. Initially, max will hold 15. Recursive through left subtree.

max = 15, leftMax = 20 => (20 > 15) then max = 20  

max = 20, leftMax = 74 => (74 > 20) then max = 74  

Recursive through right subtree.

max = 74, rightMax = 35 => (74 > 35) then max = 74  

Recurse in the left subtree of 35

max = 74, leftMax = 55 => (74 > 55) then max = 74  

Recurse in the right subtree of 35

max = 74, rightMax = 6 => (74 > 6) then max = 74  

So, the largest node in above binary tree is 74.

Algorithm

  1. Define the class Node which has three attributes namely: data, left, and right. Here, left represents the left child of the node and right represents the right child of the node.
  2. Assign the data part of the node with an appropriate value and assign left and right to null.
  3. Define another class which has an attribute root.
    1. Root represents the root node of the tree which is initialized to null.
    2. largestElement() will find out the largest node in the binary tree:
      1. It checks whether the root is null, which means the tree is empty.
      2. If the tree is not empty, define a variable max that will store temp's data.
      3. Find out the maximum node in the left subtree by calling largestElement() recursively. Store that value in leftMax. Compare the value of max with leftMax and store the maximum of two to max.
      4. Find out the maximum node in right subtree by calling largestElement() recursively. Store that value in rightMax. Compare the value of max with rightMax and store the maximum of two to max.
      5. In the end, max will hold the largest node in the binary tree.

Input:

 

Output:

Largest element in the binary tree: 74
Python programming, Php programming, Java programming, C programming, c# programming, examples, Python programming examples, Php programming examples, Java programming examples, C programming examples, c# programming examples,
login and add your own answer to this question

All Answers

robaa
2022-11-09
need an explanation for this answer? contact us directly to get an explanation for this answer

Python

#Represent a node of binary tree  
class Node:  
    def __init__(self,data):  
        #Assign data to the new node, set left and right children to None  
        self.data = data;  
        self.left = None;  
        self.right = None;  
   
class LargestNode:  
    def __init__(self):  
        #Represent the root of binary tree  
        self.root = None;  
          
    #largestElement() will find out the largest node in the binary tree  
    def largestElement(self, temp):  
        #Check whether tree is empty  
        if(self.root == None):  
            print("Tree is empty");  
            return 0;  
              
        else:      
            #Variable maximum will store temp's data  
            maximum = temp.data;  
              
            #It will find largest element in left subtree  
            if(temp.left != None):  
                leftMax = self.largestElement(temp.left);  
                #Compare variable maximum with leftMax and store greater value into maximum  
                maximum = max(maximum, leftMax);  
              
            #It will find largest element in right subtree  
            if(temp.right != None):  
                rightMax = self.largestElement(temp.right);  
                #Compare variable maximum with rightMax and store greater value into maximum  
                maximum = max(maximum, rightMax);  
              
            return maximum;  
   
bt = LargestNode();  
#Add nodes to the binary tree  
bt.root = Node(15);  
bt.root.left = Node(20);  
bt.root.right = Node(35);  
bt.root.left.left = Node(74);  
bt.root.right.left = Node(55);  
bt.root.right.right = Node(6);  
   
#Display largest node in the binary tree  
print("Largest element in the binary tree: " + str(bt.largestElement(bt.root)));

 

Output:

Largest element in the binary tree: 74

 

C

#include <stdio.h>  
#include <stdbool.h>  
#include <stdlib.h>  
   
//Represent a node of binary tree  
struct node{  
    int data;  
    struct node *left;  
    struct node *right;  
};  
   
//Represent the root of binary tree  
struct node *root = NULL;  
   
//createNode() will create a new node  
struct node* createNode(int data){  
    //Create a new node  
    struct node *newNode = (struct node*)malloc(sizeof(struct node));  
    //Assign data to newNode, set left and right children to NULL  
    newNode->data = data;  
    newNode->left = NULL;  
    newNode->right = NULL;  
      
    return newNode;  
}  
   
//largestElement() will find out the largest node in the binary tree  
int largestElement(struct node *temp){  
    //Check whether tree is empty  
    if(root == NULL) {  
        printf("Tree is empty\n");  
        return 0;  
    }  
    else{  
        int leftMax, rightMax;  
        //Max will store temp's data  
        int max = temp->data;  
        //It will find largest element in left subtree  
        if(temp->left != NULL){  
            leftMax = largestElement(temp->left);  
            //Compare max with leftMax and store greater value into max  
            max = (max > leftMax) ? max : leftMax;  
        }  
        
        //It will find largest element in right subtree  
        if(temp->right != NULL){  
          rightMax = largestElement(temp->right);  
          //Compare max with rightMax and store greater value into max  
          max = (max > rightMax) ? max : rightMax;  
        }  
    return max;  
    }  
}  
   
int main()  
{  
    //Add nodes to the binary tree  
    root = createNode(15);  
    root->left = createNode(20);  
    root->right = createNode(35);  
    root->left->left = createNode(74);  
    root->right->left = createNode(55);  
    root->right->right = createNode(6);  
          
    //Display largest node in the binary tree  
    printf("Largest element in the binary tree: %d", largestElement(root));  
    return 0;  
}

 

Output:

Largest element in the binary tree: 74

 

JAVA

public class LargestNode {  
    //Represent the node of binary tree  
    public static class Node{  
        int data;  
        Node left;  
        Node right;  
          
        public Node(int data){  
            //Assign data to the new node, set left and right children to null  
            this.data = data;  
            this.left = null;  
            this.right = null;  
        }  
     }  
        
      //Represent the root of binary tree  
      public Node root;  
        
      public LargestNode(){  
        root = null;  
      }  
        
      //largestElement() will find out the largest node in the binary tree  
      public int largestElement(Node temp){  
          //Check whether tree is empty  
           if(root == null) {  
               System.out.println("Tree is empty");  
               return 0;  
            }  
           else{  
               int leftMax, rightMax;  
               //Max will store temp's data  
               int max = temp.data;  
                  
               //It will find largest element in left subtree  
               if(temp.left != null){  
                   leftMax = largestElement(temp.left);  
                   //Compare max with leftMax and store greater value into max  
                   max = Math.max(max, leftMax);  
                }  
                  
                //It will find largest element in right subtree  
                if(temp.right != null){  
                    rightMax = largestElement(temp.right);  
                    //Compare max with rightMax and store greater value into max  
                    max = Math.max(max, rightMax);  
                }  
                return max;  
           }  
      }  
        
      public static void main(String[] args) {  
          
        LargestNode bt = new LargestNode();  
        //Add nodes to the binary tree  
        bt.root = new Node(15);  
        bt.root.left = new Node(20);  
        bt.root.right = new Node(35);  
        bt.root.left.left = new Node(74);  
        bt.root.right.left = new Node(55);  
        bt.root.right.right = new Node(6);  
          
        //Display largest node in the binary tree  
        System.out.println("Largest element in the binary tree: " + bt.largestElement(bt.root));  
      }  
}

 

Output:

Largest element in the binary tree: 74

 

C#

using System;   
namespace Tree   
{                       
    public class Program  
    {  
        //Represent a node of binary tree  
        public class Node<T>{  
            public T data;  
            public Node<T> left;  
            public Node<T> right;  
              
            public Node(T data) {  
                //Assign data to the new node, set left and right children to null  
                this.data = data;  
                this.left = null;  
                this.right = null;  
            }  
        }  
          
        public class LargestNode<T> where T : IComparable<T>{  
            //Represent the root of binary tree  
            public Node<T> root;  
   
            public LargestNode(){  
                root = null;  
            }  
              
        //largestElement() will find out the largest node in the binary tree  
        public T largestElement(Node<T> temp){  
            //Check whether tree is empty  
            if(root == null) {  
               Console.WriteLine("Tree is empty");  
               return default(T);  
            }  
            else{  
                T leftMax, rightMax;  
                //Max will store temp's data  
                T max = temp.data;  
   
                //It will find largest element in left subtree  
                if(temp.left != null){  
                  leftMax = largestElement(temp.left);  
                  //Compare max with leftMax and store greater value into max  
                  max = (max.CompareTo(leftMax) < 0) ? leftMax : max;  
                }  
   
                //It will find largest element in right subtree  
                if(temp.right != null){  
                  rightMax = largestElement(temp.right);  
                //Compare max with rightMax and store greater value into max  
                  max = (max.CompareTo(rightMax) < 0) ? rightMax : max;  
                }  
                return max;  
            }  
        }  
    }  
          
    public static void Main()  
    {  
        LargestNode<int> bt = new LargestNode<int>();  
        //Add nodes to the binary tree  
        bt.root = new Node<int>(15);  
        bt.root.left = new Node<int>(20);  
        bt.root.right = new Node<int>(35);  
        bt.root.left.left = new Node<int>(74);  
        bt.root.right.left = new Node<int>(55);  
        bt.root.right.right = new Node<int>(6);  
   
        //Display largest node in the binary tree  
        Console.WriteLine("Largest element in the binary tree: " + bt.largestElement(bt.root));  
        }      
    }  
}

 

Output:

Largest element in the binary tree: 74

 

PHP

<!DOCTYPE html>  
<html>  
<body>  
<?php  
//Represent a node of binary tree  
class Node{  
    public $data;  
    public $left;  
    public $right;  
      
    function __construct($data){  
        //Assign data to the new node, set left and right children to NULL  
        $this->data = $data;  
        $this->left = NULL;  
        $this->right = NULL;  
    }  
}  
class LargestNode{  
    //Represent the root of binary tree  
    public $root;  
    function __construct(){  
        $this->root = NULL;  
    }  
      
    //largestElement() will find out the largest node in the binary tree  
    function largestElement($temp){  
      //Check whether tree is empty  
       if($this->root == NULL) {  
           print "Tree is empty<br>";  
           return 0;  
        }  
       else{  
           //$max will store $temp's data  
           $max = $temp->data;  
             
           //It will find largest element in left subtree  
           if($temp->left != NULL){  
               $leftMax = $this->largestElement($temp->left);  
               //Compare $max with $leftMax and store greater value into $max  
               $max = max($max, $leftMax);   
            }  
              
            //It will find largest element in right subtree  
            if($temp->right != NULL){  
                $rightMax = $this->largestElement($temp->right);  
                //Compare $max with $rightMax and store greater value into $max  
                $max = max($max, $rightMax);  
            }  
           return $max;  
       }  
    }   
}  
$bt = new LargestNode();  
//Add nodes to the binary tree  
$bt->root = new Node(15);  
$bt->root->left = new Node(20);  
$bt->root->right = new Node(35);  
$bt->root->left->left = new Node(74);  
$bt->root->right->left = new Node(55);  
$bt->root->right->right = new Node(6);  
   
//Display largest node in the binary tree  
print "Largest element in the binary tree: " . $bt->largestElement($bt->root);        
?>  
</body>  
</html>

 

Output:

Largest element in the binary tree: 74

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Tree Programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Program to find the maximum depth or height of a t... >>
<< Program to find maximum width of a binary tree...