# Binary Tree – Is Balanced? – Java

This is a basic algorithm for determining whether or not a binary tree is balanced.

### How it Works

This algorithm builds on the Binary Tree Depth problem, and is just slightly more complex. From the referenced tree depth problem, the depth of a binary tree is equal to the level of its deepest node.

A binary tree is considered balanced if at any level, the left sub-tree is balanced, and the right sub-tree is balanced, and the difference between the height of the left sub-tree and right sub-tree is no more than 1. For this to make more sense, consider that every node in a binary tree is actually a smaller binary tree. At its simplest case, a leaf is a tree of size 1, and it is balanced because the depth of its left and right sub-trees is equal (0). So, if we ever find a sub-tree (non-leaf) where there is depth 2 on the left and 0 on the right, or vice-versa, that sub-tree is not balanced, and thus the entire tree is not balanced. In essence, we’re just recursively making sure that the depth of the sub-trees at any level varies by no more than 1.

### Sample Implementation

Here is a sample implementation. You may double-click to copy the contents of the sample into your IDE so that you may play with it in a debugger to learn more.

```public class BinaryTree {

//A simple class ot represent a node in the binary tree.
private static class Node {
public Node(int v) { this.value = v; }
int value;
Node left;
Node right;
}

//This main method demonstrates the isBalanced function.
public static void main(String[] args) {

//Create a tree where the largest depth is 5 on the left.
Node root = new Node(5);
root.left = new Node(3);
root.left.right = new Node(4);
root.left.left = new Node(2);
root.left.left.left = new Node(1);

//We'll give the right side maximum depth 3.
root.right = new Node(7);
root.right.left = new Node(6);
root.right.right = new Node(8);
root.right.right = new Node(9);

//Check if the tree is balanced (it is).
System.out.println(isBalanced(root));

//Unbalance the tree and recheck (will fail).
root.left.left.left.left = new Node(0);
System.out.println(isBalanced(root));
}

//Determine if the given tree is balanced by recursively
//checking if each subtree is balanced, and if the depth
//of the subtrees varies by no more than 1.
public static boolean isBalanced(Node root) {

//A null tree is considered balanced.
if (root == null) return true;

return
//The depth difference between the  left and right
//subtrees is no more than 1.
(Math.abs(depth(root.left) - depth(root.right)) < 2)

//and both subtrees are balanced.
&& isBalanced(root.left) && isBalanced(root.right);
}

//This a recursive function for finding the depth of a tree.
//The trick here is that as we recurse down to the next level
//of the tree in each case, we add 1 to the depth.  We also
//make sure that we only track the maximum depth between the
//two subtrees as that is all we care about.
public static int depth(Node root) {
if (root == null) return 0;
return 1 + Math.max(depth(root.left), depth(root.right));
}
}
```

### Output of Example

This example simply outputs “true \n false” as the tree is balanced in the first check, and it is not balanced in the second check.