To check if a binary tree is balanced.For this,a balanced tree is defined to be a tree such that the heights of the two sub-tree of any node never differ by more than one.

Solution Approach:

Point to be noted here is two sub tree differ in height by no more than one.So we can simply recurs through the entire tree,and for each node,compute the height of each sub tree.

Implementation:

public static int getHeight(TreeNode root)
{
if(root == null)
return 0;

return Math.max(getHeight(root.left), getHeight(root.right)) +1 ;
}

public static boolean isBalanced(TreeNode root)
{
if(root == null)
return 0;

int heightDiff=getHeight(root.left) - getHeight(root.right);
if(Math.abs(heightDiff) > 1)
{
return false;
}

else
{
return isBalanced(root.left) && isBalanced(root.right);
}

}

This solution is not that efficient.

Complexity will be o(Nlog N) because each node is touched once and getHeight is called repetedly on the same node.