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

### 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)