Check Whether the tree is Balanced Tree or Not

A tree is a balanced tree, if the heights of the left and right sub trees differ by at max 1 at all the nodes.

The code which checks only at the root level

bool IsTreeBalanced(Node root)
{
  if(root == NULL)
    return true;
  int lh = GetDepth(root -> left);
  int rh = GetDepth(root -> right);
  if(lh - rh > 1 || rh - lh > 1)
     return false;
  return true;
}

int GetDepth(Node root) 
{
   if(root == NULL)
      return 0;
   int lh = GetDepth(root->left);
   int rh = GetDepth(root->right);
   return (lh > rh ? lh + 1 : rh + 1);
}

The code which checks at all the levels, but, not optimized

bool IsTreeBalanced(Node root)
{
  if(root == NULL)
    return true;
  int lh = GetDepth(root -> left);
  int rh = GetDepth(root -> right);
  if(lh - rh > 1 || rh - lh > 1 || ! IsTreeBalanced(root->left) || ! IsTreeBalanced(root->right))
     return false;
  return true;
}

int GetDepth(Node root) 
{
   if(root == NULL)
      return 0;
   int lh = GetDepth(root->left);
   int rh = GetDepth(root->right);
   return (lh > rh ? lh + 1 : rh + 1);
}

The code which checks at all the levels, and optimized little

This code does not give the accurate height. If at few levels itself, if it finds that, it is not balanced, it would just return.

In C#, we can use out parameters. In C, C++, we can use pointers, and in java, we need to have some kind of holder class.

bool IsTreeBalanced(Node root, out int height)
{
  if(root == NULL) {
    height = 0;
    return true;
  }
  int lh, rh;
  if(! IsTreeBalanced(root -> left, out lh)) {
    height = lh + 1;
    return false;
  }
  if(! IsTreeBalanced(root -> right, out rh)) {
    height = (lh > rh ? lh + 1 : rh + 1);
    return false;
  }

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

  if(lh - rh > 1 || rh - lh > 1)
     return false;
  return true;
}

Very strict Balanced Tree: (In practice, not advisable)

Where the the path length of the nearest empty child is within one from the path to the farthest empty child.

bool IsTreeBalanced(Node root)
{
  int max = GetMaxMinDepth(root, min);
  if(max - min > 1)
     return false;
  return true;
}

int GetMaxMinDepth(Node root, out int minDepth) 
{
   if(root == NULL) {
      minDepth = 0;
      return 0;
   }
   int lmin, rmin;
   int lmax = GetMaxMinDepth(root->left, out lmin);
   int rmax = GetMaxMinDepth(root->right, out rmin);
   minDepth = lmin < rmin ? lmin + 1 : rmin + 1;
   return (lmax > rmax ? lmax + 1 : rmax + 1);
}