Compute Height of a Binary Tree

Compute Height of a Binary Tree” is a very basic problem of Tree data structure. Here, we are given a Binary Tree and our task is to compute height of given binary tree. The height of the tree is defined as total number of nodes in a longest path from root node to any leaf node.

compute height of a binary tree
Height of a Binary Tree

We can compute height of a binary tree using recursion. The steps/algorithm to compute height of a binary tree is as follows:

  1. If Tree is empty, then return 0 as height of tree.
  2. Else:
    1. Compute Maximum depth of left subtree recursively.
    2. Compute Maximum depth of right subtree recursively.
    3. Compute max of max depths of left and right subtrees and add 1 to it for the current node.
    4. Return max_depth.
height of a binary tree
Recursive Calculation to Calculate Height of Binary Tree

C++ Program to compute height of a binary tree is as follows:

/* C++ Program to Compute Height of a Binary Tree */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to Compute height of a Binary Tree */
int height(Node *root)
{
    /* If tree is empty, height will be 0 */
    if(root == NULL)
    {
        return 0;
    }
    else
    {
        /* Compute Height of Left Subtree */
        int leftHeight = height(root -> left);
        
        /* Compute Height of Right Subtree */
        int rightHeight = height(root -> right);
        
        /* Return max of height of subtree and right subtree + 1 */
        return max(leftHeight,rightHeight) + 1;
    }
}

int main()
{
    /* Creating a Binary tree and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling and Printing Height of Binary Tree */
    cout<<"The Height of Given Binary Tree is "<<height(root);
}

OUTPUT:

The Height of Given Binary Tree is 4

Related Posts:

  1. Introduction to Tree Data Structure
  2. Binary Tree Traversals
  3. Print All Leaf Nodes of a Binary Tree
  4. Count Number of Nodes in a Binary Tree
  5. Print Alternate Levels of Binary Tree
  6. Maximum Width of Binary Tree
  7. Level Order Tree Traversal
  8. Left View of Binary Tree
  9. Right View of Binary Tree
  10. Inorder Tree Traversal Using Stack
  11. Preorder Tree Trasversal Using Stack
  12. Postorder Tree Traversal Using Stack
  13. Vertical Order Tree Traversal
  14. Top View of Binary Tree
  15. Bottom View of Binary Tree
  16. Delete Complete Binary Tree
  17. Check if two trees are mirror Trees of Each Other
  18. Convert Binary Tree to its Mirror Tree
  19. Check if Binary Tree is Symmetric or Not
  20. Print All Root to Leaf Paths in a Binary Tree

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *