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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s