Program to Find Maximum Depth or Height of a Binary Tree

• Write a C program to find maximum depth of a binary tree.
• Function to print height of a binary tree.

The height of a tree is the number of nodes from the root node to the deepest leaf. To find the height of a binary tree, we will take maximum of left and right sub tree height + 1. For Example:

Given Binary Tree
            1  <--Root
           / \
         2    3
        /    / \
       4    8   6
Height of Binary Tree : 3 

In this program, we will use recursion to find the height of a binary tree. Finding the height of binary tree can be divided to two sub problems of finding the height of left and right sub tree.

Height of Tree = Maximum of(left Sub tree height , right sub tree height) + 1;

---

Algorithm to find maximum depth of a binary tree
Let "root" be the pointer to a root node of a binary tree and "getHeight" function returns height of tree.

• Recursion termination condition : If root is equal to NULL, return 0;
• Recursively, find the height of left sub tree(getHeight(root->left). Let it be leftHeight.
• Recursively, find the height of right sub tree(getHeight(root->right). Let it be rightHeight.
• Return Maximum of(leftHeight, rightHeight) + 1

In this program, we will use "getHeight" function which takes pointer to a root node of binary tree and returns it's height by implementing above algorithm.

int getHeight(struct node *root){
    int leftHeight, rightHeight;
    if(root == NULL)
        return 0;
    leftHeight = getHeight(root->left);
    rightHeight = getHeight(root->right);
    
    return getMax(leftHeight, rightHeight) + 1;
}

---

C program to find height of a binary tree

#include <stdio.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below 
            1
           / \
         2    3
        / \  / \
       4  5 6  7
      /
     8
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
    // Level 2 nodes 
    root->left = getNewNode(2);
    root->right = getNewNode(3);
    // Level 3 nodes
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->left = getNewNode(6);
    root->right->right = getNewNode(7);
    // Level 4 nodes
    root->left->left->left = getNewNode(8);
    
    return root;

}
/* Returns maximum of two given numbers */
int getMax(int a, int b){
    if(a >= b)
        return a;
    else 
        return b;
}
/*
Returns total number of nodes(size) in a bianry tree
getHeight(root) = Maximum of (getHeight(left-subTree), 
  getHeight(right-subTree)) + 1;
*/
int getHeight(struct node *root){
    int leftHeight, rightHeight;
    if(root == NULL)
        return 0;
    leftHeight = getHeight(root->left);
    rightHeight = getHeight(root->right);
    
    return getMax(leftHeight, rightHeight) + 1;
}

int main() {
    struct node *root = generateBTree();    
    
    printf("Height of Tree = %d", getHeight(root));
    
    getchar();
    return 0; 
}

Output

Height of Tree = 4