Q:

Program to find the maximum depth or height of a tree

belongs to collection: Tree Programs

0

Explanation

In 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.
Height of right subtree is 4.
MaxHeight = Max(leftHeight, rightHeight) + 1; Here, 1 Represents root node's height

The maximum height of the given binary tree is (4 + 1) = 5 denoted by white dotted line.

Algorithm

  1. Define Node class 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. When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
  3. Define another class which has an attribute root.
    1. Root represents the root node of the tree and initializes it to null.
  4. findHeight() will determine the maximum height of the binary tree:
    1. It checks whether the root is null, which means the tree is empty.
    2. If the tree is not empty, traverse through left subtree to determine the height of the left subtree and store the value in leftHeight.
    3. Similarly, determine the height of the right subtree and store the value in rightHeight.
    4. Maximum will determine the maximum of leftHeight and rightHeight then, add 1 for root's height.

Input:

Output:

Maximum height of given binary tree: 5

All Answers

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 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

 

JAVA

public 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

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

total answers (1)

Program to find the nodes which are at the maximum... >>
<< Program to find the largest element in a Binary Tr...