Press "Enter" to skip to content

How to check if a tree is balanced in Java

Ajk 7

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]

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]

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 🙂