## 09/04/2017

### [Java] Find if a binary tree is balanced

A binary tree is balanced if the left and right branches do not differ in depth for more than one level.

Here is some code to test this (isTreeBalanced) you can check on my Gist for some test cases as well:

`````` /*
is tree balanced
A tree is balanced if the left and right branches do not differ for more than 1 level in length
*/
private static Entry isTreeBalancedAux(BST root){
//null root is always balanced
if(root == null) return new Entry(true, -1);

Entry left, right;

//check subtrees
left = isTreeBalancedAux(root.left);
right = isTreeBalancedAux(root.right);

//if they are not balanced, we have our answer
if(!left.isBalanced || !right.isBalanced) return new Entry(false, 0);

//otherwise if they are balanced, but they differ for more than 1 level in depth, this node is not balanced
if(Math.abs(left.height - right.height) > 1) return new Entry(false, 0);

//finally, if all is good, return the max depth from this node incuding itself and mark it as balanced
return new Entry(true, Math.max(left.height, right.height) + 1);
}

public static boolean isTreeBalanced(BST root){
return isTreeBalancedAux(root).isBalanced;
}
``````

I use an additional data structure (Entry) to pass around two pieces of information:

- is the tree balanced so far
- what is the current depth of the path being analyzed