CareerCup

Here is a neat code to check whether a tree is balanced or not,

puddleofriddles.blogspot.com/search?q=balanced

int maxDepth(node* root)
{
if(NULL == root)
return 0;

int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);

return 1 + (leftDepth > rightDepth ? leftDepth:rightDepth);
}

int minDepth(node* root)
{
if(NULL == root)
return 0;

int leftDepth = minDepth(root->left);
int rightDepth = minDepth(root->right);

return 1 + (leftDepth < rightDepth ? leftDepth:rightDepth);
}

int isBalanced(node* root)
{
if(maxDepth(root) - minDepth(root) > 1)
return 0;
else
return 1;
}

int checkBalance(Node n, Boolean flag) {

  if(n == null) return -1;
  
  int leftHeight = checkBalance(n.left) + 1;
  int rightHeight = checkBalance(n.right) + 1;

  if(Math.Abs(leftHeight - rightHeight) > 1) flag = true;

  return max(leftHeight, rightHeight);

}

bool isBalance(Node n) {

  Boolean flag = false;
  checkBalance(n);
  return flag;

}