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.
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.
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;
Time complexity is O(N)
Space complexity is O( log N)