Home » Problem Solving » How to check if a tree is balanced in Java

How to check if a tree is balanced in Java

When I first stumbled upon this question, I immediately made a TreeNode implementation and tried to write down the solution.
As it turns out, I forgot one important step of problem solving – Clarifications! What does it mean for a tree to be balanced. I did a bit of research online and it turns out to different people it means different things.

As this excellent article on stackexchange explains we have 2 different definitions:

A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

  1. The first definition is otherwise called [weight-balanced] (This is also the definition that wikipedia uses for balanced binary tree)
  2. The second definition is otherwise called [height-balanced] and weirdly enough is the one most interviewers are asking for.

To cut to the chase we will try to give an elegant solution for both, so next time you hear this on an interview, me and you can both ace it ;D.

How to check if a tree is balanced in Java – [Height]

/*
 * @Author: Ajk Palikuqi
 * 
 * @Question: How to check if a tree is balanced in Java
 * 
 */

package iqLib.treeLib;

public class TreeHeightBalanced
{
   public static boolean isHeightBalanced(TreeNode root)
   {
      return (maxLeafHeight(root) - minLeafHeight(root)) <= 1;
   }
   
   public static int maxLeafHeight(TreeNode root)
   {
      if (root == null)
      {
         return 0;
      }
      
      return Math.max(maxLeafHeight(root.getLeft()), maxLeafHeight(root.getRight())) + 1;
   }
   
   public static int minLeafHeight(TreeNode root)
   {
      if (root == null)
      {
         return 0;
      }
      
      return Math.min(minLeafHeight(root.getLeft()), minLeafHeight(root.getRight())) + 1;
   }
}

Yay, one down. The next one is a bit more tricky. We could write a boolean recursive method, but that way we would check the nodes multiple times anytime we're getting the height of a subtree. Instead we will try to count only weight balanced subtree heights. If the subtree is not balanced we return -1 to keep track of it.

How to check if a tree is balanced in Java - [Weight]

/*
 * @Author: Ajk Palikuqi
 * 
 * @Question: How to check if a tree is balanced in Java
 * 
 */

package iqLib.treeLib;

public class TreeWeightBalanced
{
   public static boolean isWeightBalanced(TreeNode root)
   {
      if (getBalancedHeight(root) == -1)
      {
         return false;
      }

      return true;
   }

   /*
    * Given a TreeNode root, return the height of the tree under it if it is
    * balanced. Return -1 otherwise.
    */
   public static int getBalancedHeight(TreeNode root)
   {
      if (root == null)
      {
         return 0;
      }

      int leftBalancedHeight = getBalancedHeight(root.getLeft());
      int rightBalancedHeight = getBalancedHeight(root.getRight());

      if ((Math.abs(leftBalancedHeight - rightBalancedHeight) > 1) || 
            (leftBalancedHeight == -1) || (rightBalancedHeight == -1))
      {
         return -1;
      }
      
      return Math.max(leftBalancedHeight, rightBalancedHeight);
   }
}

As you can see we added some getters to our TreeNode class to get the left and right child node. (Yes I did update the page here too)

All code as always can be found at my GitHub repository so you can make a pull if you wanna test in on your own.

Hope you guys enjoyed it... and I'll see you guys next time ;D.

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media :)
  • Keaton Greve

    Nice article. Just wanted to point out that on line 34 of your second code snippet, you wrote root.getLeft() but you should have put root.getRight().

    • http://www.FitCoding.com/ Ajk_P

      Good catch! I am horrible at typos. Fixed!

%d bloggers like this: