C Program to Check Whether a Binary Tree is Height Balanced or Not

• Write a C program to check if a binary tree is height balanced.

Given a binary tree we have to check whether binary tree is height balanced or not. A binary tree is height balanced if the difference between the height of left and right sub tree is not more than 1. Height balancing of binary tree is done to avoid skewed tree and to maintain proper distribution of nodes on every level.

---

Algorithm to check binary tree is height balanced or not
Let "node" be the pointer to any node of given binary tree.

• If node is equal to NULL, then return true. An empty tree is height balanced tree.
• If node is a leaf node, then return true.
• Calculate the height of left and right sub tree. Let it be leftTreeHeight and rightTreeHeight.
• Check if the difference between leftTreeHeight and rightTreeHeight is <= 1 and left and right sub tree both are height balanced or not.
• If all three condition mentioned above is true then sub tree rooted at "node" is height balanced tree else not a height balanced tree.

Time Complexity : O(n²)

---

C program check height balanced binary tree

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define TRUE 1
#define FALSE 0

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 tree
            1
           / \
         9    12
        / \    \
       4  50    -7
      / \
     18  9
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
 
    root->left = getNewNode(9);
    root->right = getNewNode(12);
 
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(50);
    root->right->right = getNewNode(-7);

    root->left->left->left = getNewNode(18);
    root->left->left->right = getNewNode(9);
    
    return root;

}

/* Returns Maximum of two numbers */
int getMax(int a, int b){
 if(a >= b)
     return a;
 else 
     return b;
}

/* Returns Height of binary tree */
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;
}

/* Check is passed binary tree is height-balanced */
int isHeightBalanced(struct node *root){
   int leftHeight, rightHeight;
 
   /* Empty Tree is always height balanced */
   if(root == NULL)
       return TRUE; 
 
   /* Find the height of left and right subtree */
   leftHeight = getHeight(root->left);
   rightHeight = getHeight(root->right);
   
   /* If both sub trees are height balanced and the 
   difference of height of left and right subtree is <= 1,
    then given tree is Height balanced else not */
   if(abs(leftHeight - rightHeight) <= 1 &&
       isHeightBalanced(root->right) &&
       isHeightBalanced(root->left))
       return TRUE;
   else 
       return FALSE;
}

int main() {
    struct node *clone, *root = generateBTree();    
    
    if(isHeightBalanced(root)){
     printf("Height Balanced Tree\n");
    } else {
 printf("Not a Height Balanced Tree\n");
    }
 
    /* Modifying tree to make it un Balanced Tree */
    root->right->right = NULL;
 
    if(isHeightBalanced(root)){
     printf("Height Balanced Tree\n");
    } else {
 printf("Not a Height Balanced Tree\n");
    }
    
    getchar();
    return 0; 
}

Output

Height Balanced Tree
Not a Height Balanced Tree