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.