Problem statement

Check if a Binary Tree is Balanced in O(N) time complexity.

Assumption: Heights of two subtrees of any node should never differ by more than one, to consider a tree as balanced.

Approach

We can use a recursive function that will return the height of its subtree, or a special integer (-1) if the node is not balanced.

In every recusrive call, 

if node is null, then return 0.

if any subtree return -1 or difference of height of left and right subtree is more than 1, then return -1.

if all is well, return the max height (out left and right tree) + 1.

Solution

int checkHeight(TreeNode n)

{

  if( n == null ) return 0;

 

  int leftHeight = checkHeight( n.left );

  if (leftHeight == -1) return -1;

 

  int rightHeight = checkHeight( n.right );

  if (rightHeight == -1) return -1;

 

  if (Math.absolute ( leftHeight - rightHeight ) > 1 ) return -1;

 

  return Math.max ( leftHeight, rightHeight) + 1;

 

}

Complexities

Time complexity is O(N)

Space complexity is O( log N)