Binary Tree / data structure

Compute Height of a Binary Tree

by admin · January 22, 2021

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

If Tree is empty, then return 0 as height of tree.
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:

You may also like...