Expand Authors Top

If you have a few years of experience in the Java ecosystem and you’d like to share that with the community, have a look at our Contribution Guidelines.

Expanded Audience – Frontegg – Security (partner)
announcement - icon User management is very complex, when implemented properly. No surprise here.

Not having to roll all of that out manually, but instead integrating a mature, fully-fledged solution - yeah, that makes a lot of sense.
That's basically what Frontegg is - User Management for your application. It's focused on making your app scalable, secure and enjoyable for your users.
From signup to authentication, it supports simple scenarios all the way to complex and custom application logic.

Have a look:

>> Elegant User Management, Tailor-made for B2B SaaS

November Discount Launch 2022 – Top
We’re finally running a Black Friday launch. All Courses are 30% off until end-of-day today:


November Discount Launch 2022 – TEMP TOP (NPI)
We’re finally running a Black Friday launch. All Courses are 30% off until end-of-day today:


1. Overview

Trees are one of the most important data structures in computer science. We're usually interested in a balanced tree, because of its valuable properties. Their structure allows performing operations like queries, insertions, deletions in logarithmic time.

In this tutorial, we're going to learn how to determine if a binary tree is balanced.

2. Definitions

First, let's introduce a few definitions in order to make sure we're on the same page:

  • A binary tree – a kind of a tree where every node has zero, one or two children
  • A height of a tree – a maximum distance from a root to a leaf (same as the depth of the deepest leaf)
  • A balanced tree – a kind of a tree where for every subtree the maximum distance from the root to any leaf is at most bigger by one than the minimum distance from the root to any leaf

We can find an example of a balanced binary tree below. Three green edges are a simple visualization of how to determine the height, while the numbers indicate the level.

binary tree

3. Domain Objects

So, let's start with a class for our tree:

public class Tree {
    private int value;
    private Tree left;
    private Tree right;

    public Tree(int value, Tree left, Tree right) {
        this.value = value;
        this.left = left;
        this.right = right;

For the sake of simplicity, let's say each node has an integer value. Note, that if left and right trees are null, then it means our node is a leaf.

Before we introduce our primary method let's see what it should return:

private class Result {
    private boolean isBalanced;
    private int height;

    private Result(boolean isBalanced, int height) {
        this.isBalanced = isBalanced;
        this.height = height;

Thus for every single call, we'll have information about height and balance.

4. Algorithm

Having a definition of a balanced tree, we can come up with an algorithm. What we need to do is to check the desired property for every node. It can be achieved easily with recursive depth-first search traversal.

Now, our recursive method will be invoked for every node. Additionally, it will keep track of the current depth. Each call will return information about height and balance.

Now, let's take a look at our depth-first method:

private Result isBalancedRecursive(Tree tree, int depth) {
    if (tree == null) {
        return new Result(true, -1);

    Result leftSubtreeResult = isBalancedRecursive(tree.left(), depth + 1);
    Result rightSubtreeResult = isBalancedRecursive(tree.right(), depth + 1);

    boolean isBalanced = Math.abs(leftSubtreeResult.height - rightSubtreeResult.height) <= 1;
    boolean subtreesAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced;
    int height = Math.max(leftSubtreeResult.height, rightSubtreeResult.height) + 1;

    return new Result(isBalanced && subtreesAreBalanced, height);

First, we need to consider the case if our node is null: we'll return true (which means the tree is balanced) and -1 as a height.

Then, we make two recursive calls for the left and the right subtree, keeping the depth up to date.

At this point, we have calculations performed for children of a current node. Now, we have all the required data to check balance:

  • the isBalanced variable checks the height for children, and
  • substreesAreBalanced indicates if the subtrees are both balanced as well

Finally, we can return information about balance and height. It might be also a good idea to simplify the first recursive call with a facade method:

public boolean isBalanced(Tree tree) {
    return isBalancedRecursive(tree, -1).isBalanced;

5. Summary

In this article, we've discussed how to determine if a binary tree is balanced. We've explained a depth-first search approach.

As usual, the source code with tests is available over on GitHub.

November Discount Launch 2022 – Bottom
We’re finally running a Black Friday launch. All Courses are 30% off until end-of-day today:


Generic footer banner
Comments are closed on this article!