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) + 1;
   }
}

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 :)

Latest posts by Ajk (see all)

  • 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!

  • Gautham

    Hy ,

    I have question regarding the first snippet ,this solution just seems to check the root what about the left subtree and right subtree ?
    i guess there should be a condition like this ,

    return ((maxLeafHeight(root) – minLeafHeight(root)) <= 1 && isHeightBalanced(root.getLeft()) && isHeightBalanced(root.getRight());

    Also i feel the base condition should return -1

    if (root == null){

    return -1;

    }

    Correct me if i am wrong.

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

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

      Hence we only have to check the minimum depth leaf and maximum depth leaf. We do not have to check them for every node. (I.e. if for any two leaves the difference is one, for two leaves of a subtree the difference will also be one.). Checking for every node additionally will raise our complexity by another O(n).

      For a null input on the second one, depends on implementation. I am assuming here that a null tree has height 0 and is balanced.

  • varun gulati

    should line 42 be
    return Math.max(leftBalancedHeight, rightBalancedHeight) + 1;
    ????

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

      correct!

%d bloggers like this: