Balanced Binary Trees

Let’s dig into the beautiful world of balanced binary trees!

As we’ve seen in the previous article, binary trees help perform search operations. However, the way they are arranged significantly influences performances. Take a look at the following tree:

Tree with only right children

It does follow the definition of a BST: for each node, the left child has a lower value, and the right child has a higher value. However, you can quickly see that there are only right children. In such a case, if you wanted to search if the far right value exists, you’d have to make as many comparisons as there are nodes in the tree. In this case, to search for 70, you’d have to make 5 comparisons.

Of course, with only 5 values in the tree, it does not take a lot of time. But if you were to have the same tree structure with hundreds of millions of values, it would take a significantly longer time.

Instead of having a tree that expands only on one side, we would love to have a tree that really looks like a tree. And to make the search even more optimised, we want to ensure that we’ll always make the smallest number of comparisons possible. That’s where the concept of a balanced tree comes into action.

Before going to the definition, here are some interesting properties of a binary tree of size n:

• the maximum height will be n — 1
• the minimum height will be floor(log2(n))

Balanced Trees

A balanced binary tree is a BST that has the following properties:

• For any node, the difference in height between its left and right subtree is no more than 1
• the left subtree is balanced
• the right subtree is balanced

A balanced version of the previous tree would look like this:

Balanced Tree

As you can see, this tree is balanced. There is never a difference of more than 1 between a left and a right subtree of a node. Here, searching for the number 70 only takes 3 comparisons. And this tree has a height of 2, which is the minimum height possible for a tree of 5 nodes.

Now imagine a tree containing a million values.

Ordered as it was previously, it would have a height of 999 999.
But if it were a balanced tree, it would have a height of 19.

This means you’d have to make a maximum of 19 operations to find if a value exists in that tree. Pretty cool.

Check if a tree is balanced

As we saw before, a tree is balanced if for any node, the difference in height between its left and right subtree is no more than 1, recursively.

The function to do that will compare height. But instead of using the height function, we’ll calculate both the left and the right heights each time and compare them. If the difference is 0 or 1 in absolute value, and both subtrees are balanced, we return the actual height. In any other case, we return -1.

The function would look like this

function balanced_height(node: TreeNode)
    if node is null
        return  0
    endif
    const left = is_balanced(node.left)
    if left == -1
        return -1
    endif
    const right = is_balanced(node.right)
    if right == -1
        return -1
    endif
    if Math.abs(left - right) > 1
        return -1
    endif
    return Math.max(left, right) + 1

function is_balanced(node: TreeNode)
  return balanced_height(node) != 0

Self-balancing binary trees

Balanced trees are fantastic for getting searching done quickly. But what happens to them if you start adding values?

It is pretty easy to see that if you add values one after the other, your tree will still be a BST, but it will quickly not be balanced anymore.

Luckily, it is possible to track that. Many types of self-aware trees have been created. What they do is whenever the tree becomes unbalanced, they perform new types of operations to become balanced again.

We call those types of trees self-balancing.

In the following article, we’ll focus on one of them, the AVL Tree.

Related articles:

Binary search tree

Binary Search Trees: AVL Trees