# Check Balanced

Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.

## Link here to the repo to solve the problem

👉## 👌 Tips

Think about the definition of a balanced tree. Can you check that condition for a single node? Can you check it for every node?

If you've developed a brute force solution, be careful about its runtime. If you are computing the height of the subtrees for each node, you could have a pretty inefficient algorithm.

What if you could modify the binary tree node class to allow a node to store the height of its subtree?

You don't need to modify the binary tree class to store the height of the subtree. Can your recursive function compute the height of each subtree while also checking if a node is balanced? Try having the function return multiple values.

Actually, you can just have a single checkHeight function that does both the height computation and the balance check. An integer return value can be used to indicate both .

## 👊 Solution 1

In this case we are explicitly told what a balanced tree means. Basically for each of the nodes, it's two sub-trees difference in height should not be more than 1.

In this solution we simply recurse through the entire tree, computing the height of each subtree and comparing it to the other.

```
public class IsBalanced {
boolean solution(BinaryTreeNode root) {
if (root == null) return true;
int leftHeight = checkHeight(root.left);
int rightHeight = checkHeight(root.right);
int heightDiff = leftHeight - rightHeight;
if (Math.abs(heightDiff) > 1) return false;
else return solution(root.left) && solution(root.right);
}
int checkHeight(BinaryTreeNode n) {
if (n == null) return -1;
return Math.max(checkHeight(n.left), checkHeight(n.right)) + 1;
}
}
```

This solution works. Although it wouldnt be very efficient as we recurse through the entire subtree of each node. Meaning the function checkHeight() is called repeatedly on the same nodes. The runtime is O(N log N) since each node is traversed once per node above it.

## 👊 Solution 2

In the previous method, you might have noticed that getHeight could have actually checked it the tree is balanced at the same time as it was checking for heights.

In order to do this we will need to return an error code when we discover the tree is actually is not balanced. As we are returning an int from checkHeight, we are going to return the error code of Integer.MIN_VALUE.

Lets see this approach which runs in O(N) time and uses O(H) space, where H is the height of the tree.

```
public class IsBalanced {
boolean solution(BinaryTreeNode root) {
return checkHeight(root ) != Integer.MIN_VALUE;
}
private int checkHeight(BinaryTreeNode n) {
if (n == null) return -1;
int leftHeight = checkHeight(n.left);
if (leftHeight == Integer.MIN_VALUE) return Integer.MIN_VALUE;
int rightHeight = checkHeight(n.right);
if (rightHeight == Integer.MIN_VALUE) return Integer.MIN_VALUE;
int heightDiff = leftHeight - rightHeight;
if (Math.abs(heightDiff) > 1) return Integer.MIN_VALUE;
else return Math.max(checkHeight(n.left), checkHeight(n.right)) + 1;
}
}
```

This improved algorithm works by checking the height of each subtree as we recurse down from the root. On each node, we recursively get the heights of the left and right subtrees through the checkHeight method. If the subtree is balanced, then checkHeight will return the actual height of the subtree. If the subtree is not balanced, then checkHeight will return the error code (Integer.MIN_VALUE). We will immediately break and return an error code from the current call.

*Question borrowed from “Cracking the coding interview”*