CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to find the maximum depth or height of a treeExplanationIn this program, we need to find out the maximum height of the binary tree. The height of the binary tree can be defined as the number of nodes between root and a leaf. Maximum height will be the number of levels between root and deepest leaf. To solve this problem, we traverse through the left subtree and calculate the height of the left subtree. Again, calculate the height of the right subtree by traversing through it. Maximum height will be maximum of the height of the left subtree and right subtree. In the above binary tree, Height of left subtree is 2. The maximum height of the given binary tree is (4 + 1) = 5 denoted by white dotted line. 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 BinaryTree: def __init__(self): #Represent the root of binary tree self.root = None; #findHeight() will determine the maximum height of the binary tree def findHeight(self, temp): #Check whether tree is empty if(self.root == None): print("Tree is empty"); return 0; else: leftHeight = 0; rightHeight = 0; #Calculate the height of left subtree if(temp.left != None): leftHeight = self.findHeight(temp.left); #Calculate the height of right subtree if(temp.right != None): rightHeight = self.findHeight(temp.right); #Compare height of left subtree and right subtree #and store maximum of two in variable max maximum = leftHeight if (leftHeight > rightHeight) else rightHeight; #Calculate the total height of the tree by adding the height of the root return (maximum + 1); bt = BinaryTree(); #Add nodes to the binary tree bt.root = Node(1); bt.root.left = Node(2); bt.root.right = Node(3); bt.root.left.left = Node(4); bt.root.right.left = Node(5); bt.root.right.right = Node(6); bt.root.right.right.right= Node(7); bt.root.right.right.right.right = Node(8); #Display the maximum height of the given binary tree print("Maximum height of given binary tree: " + str(bt.findHeight(bt.root))); Output: Maximum height of given binary tree: 5 C#include <stdio.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; } //findHeight() will determine the maximum height of the binary tree int findHeight(struct node *temp){ //Check whether tree is empty if(root == NULL) { printf("Tree is empty\n"); return 0; } else { int leftHeight = 0, rightHeight = 0; //Calculate the height of left subtree if(temp>left != NULL) leftHeight = findHeight(temp>left); //Calculate the height of right subtree if(temp>right != NULL) rightHeight = findHeight(temp>right); //Compare height of left subtree and right subtree //and store maximum of two in variable max int max = (leftHeight > rightHeight) ? leftHeight : rightHeight; //Calculate the total height of tree by adding height of root return (max + 1); } } int main() { //Add nodes to the binary tree root = createNode(1); root>left = createNode(2); root>right = createNode(3); root>left>left = createNode(4); root>right>left = createNode(5); root>right>right = createNode(6); root>right>right>right= createNode(7); root>right>right>right>right = createNode(8); //Display the maximum height of the given binary tree printf("Maximum height of given binary tree: %d", findHeight(root)); return 0; } Output: Maximum height of given binary tree: 5 JAVApublic class BinaryTree { //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 BinaryTree(){ root = null; } //findHeight() will determine the maximum height of the binary tree public int findHeight(Node temp){ //Check whether tree is empty if(root == null) { System.out.println("Tree is empty"); return 0; } else { int leftHeight = 0, rightHeight = 0; //Calculate the height of left subtree if(temp.left != null) leftHeight = findHeight(temp.left); //Calculate the height of right subtree if(temp.right != null) rightHeight = findHeight(temp.right); //Compare height of left subtree and right subtree //and store maximum of two in variable max int max = (leftHeight > rightHeight) ? leftHeight : rightHeight; //Calculate the total height of tree by adding height of root return (max + 1); } } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); //Add nodes to the binary tree bt.root = new Node(1); bt.root.left = new Node(2); bt.root.right = new Node(3); bt.root.left.left = new Node(4); bt.root.right.left = new Node(5); bt.root.right.right = new Node(6); bt.root.right.right.right= new Node(7); bt.root.right.right.right.right = new Node(8); //Display the maximum height of the given binary tree System.out.println("Maximum height of given binary tree: " + bt.findHeight(bt.root)); } } Output: Maximum height of given binary tree: 5 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 BinaryTree<T> where T : IComparable<T>{ //Represent the root of binary tree public Node<T> root; public static Boolean flag = false; public BinaryTree(){ root = null; } //findHeight() will determine the maximum height of the binary tree public int findHeight(Node<T> temp){ //Check whether tree is empty if(root == null) { Console.WriteLine("Tree is empty"); return 0; } else { int leftHeight = 0, rightHeight = 0; //Calculate the height of left subtree if(temp.left != null) leftHeight = findHeight(temp.left); //Calculate the height of right subtree if(temp.right != null) rightHeight = findHeight(temp.right); //Compare height of left subtree and right subtree //and store maximum of two in variable max int max = (leftHeight > rightHeight) ? leftHeight : rightHeight; //Calculate the total height of tree by adding height of root return (max + 1); } } } public static void Main() { BinaryTree<int> bt = new BinaryTree<int>(); //Add nodes to the binary tree bt.root = new Node<int>(1); bt.root.left = new Node<int>(2); bt.root.right = new Node<int>(3); bt.root.left.left = new Node<int>(4); bt.root.right.left = new Node<int>(5); bt.root.right.right = new Node<int>(6); bt.root.right.right.right= new Node<int>(7); bt.root.right.right.right.right = new Node<int>(8); //Display the maximum height of the given binary tree Console.WriteLine("Maximum height of given binary tree: " + bt.findHeight(bt.root)); } } } Output: Maximum height of given binary tree: 5 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 BinaryTree{ //Represent the root of binary tree public $root; function __construct(){ $this>root = NULL; } //findHeight() will determine the maximum height of the binary tree function findHeight($temp){ //Check whether tree is empty if($this>root == null) { print "Tree is empty <br>"; return 0; } else { $leftHeight = 0; $rightHeight = 0; //Calculate the height of left subtree if($temp>left != NULL) $leftHeight = $this>findHeight($temp>left); //Calculate the height of right subtree if($temp>right != NULL) $rightHeight = $this>findHeight($temp>right); //Compare height of left subtree and right subtree //and store maximum of two in variable max $max = ($leftHeight > $rightHeight) ? $leftHeight : $rightHeight; //Calculate the total height of tree by adding height of root return ($max + 1); } } } $bt = new BinaryTree(); //Add nodes to the binary tree $bt>root = new Node(1); $bt>root>left = new Node(2); $bt>root>right = new Node(3); $bt>root>left>left = new Node(4); $bt>root>right>left = new Node(5); $bt>root>right>right = new Node(6); $bt>root>right>right>right= new Node(7); $bt>root>right>right>right>right = new Node(8); //Display the maximum height of the given binary tree print "Maximum height of given binary tree: " . $bt>findHeight($bt>root); ?> </body> </html> Output: Maximum height of given binary tree: 5
Next TopicPrograms List
