CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to find the largest element in a Binary Tree.ExplanationIn 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 subtree 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
SolutionPython#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 JAVApublic 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
Next TopicPrograms List
