How to determine if a binary tree is height-balanced? | GeeksforGeeks

Related: LeetCode 110 - Balanced Binary Tree
Optimized implementation: Above implementation can be optimized by calculating the height in the same recursion rather than calling a height() function separately. Thanks to Amar for suggesting this optimized version. 
Post-Order: This optimization reduces time complexity to O(n).

bool isBalanced(struct node *root, int* height)

{

  /* lh --> Height of left subtree

     rh --> Height of right subtree */   

  int lh = 0, rh = 0; 

  /* l will be true if left subtree is balanced

    and r will be true if right subtree is balanced */

  int l = 0, r = 0;

  if(root == NULL)

  {

    *height = 0;

     return 1;

  }

  /* Get the heights of left and right subtrees in lh and rh

    And store the returned values in l and r */   

  l = isBalanced(root->left, &lh);

  r = isBalanced(root->right,&rh);

  /* Height of current node is max of heights of left and

     right subtrees plus 1*/   

  *height = (lh > rh? lh: rh) + 1;

  /* If difference between heights of left and right

     subtrees is more than 2 then this node is not balanced

     so return 0 */

  if((lh - rh >= 2) || (rh - lh >= 2))

    return 0;

  /* If this node is balanced and left and right subtrees

    are balanced then return true */

  else return l&&r;

}

To check if a tree is height-balanced, get the height of left and right subtrees. Return true if difference between heights is not more than 1 and left and right subtrees are balanced, otherwise return false. 

Time Complexity: O(n^2) Worst case occurs in case of skewed tree.

bool isBalanced(struct node *root)

{

   int lh; /* for height of left subtree */

   int rh; /* for height of right subtree */ 

   /* If tree is empty then return true */

   if(root == NULL)

    return 1;

   /* Get the height of left and right sub trees */

   lh = height(root->left);

   rh = height(root->right);

   if( abs(lh-rh) <= 1 &&

       isBalanced(root->left) &&

       isBalanced(root->right))

     return 1;

   /* If we reach here then tree is not height-balanced */

   return 0;

}

Read full article from How to determine if a binary tree is height-balanced? | GeeksforGeeks