Solution: Balanced Binary Tree

Solution#

A balanced binary tree is one where the heights of the left and right subtrees of each node differ by at most $1$. To check if a tree is balanced, we look at each node and calculate the heights of its left and right subtrees. If the height difference is more than $1$ at any node, it’s considered imbalanced. If all nodes have a height difference of at most $1$, the tree is considered balanced.

The steps of the abovementioned algorithm are given below:

Create a recursive helper function is_balanced_helper that returns the height of a subtree rooted at the given node. If the subtree is imbalanced, it returns $-1$. The steps of the recursive function are given below:

• If the node is NULL, return $0$ because it indicates an empty tree and the height of an empty tree is $0$.

• Calculate the height of the left subtree recursively. If the left subtree is imbalanced, we return $-1$.

• In the similar manner, calculate the height of the right subtree. If the right subtree is imbalanced, we return $-1$.

• If both left and right subtrees are balanced, we calculate the difference between the heights of the left and right subtrees. If the difference is more than $1$, we return $-1$ indicating that the current subtree is not balanced.

• If the current subtree is balanced, we return the height of this subtree by adding $1$ to the maximum height of the left and right subtrees.

The is_balanced function uses the helper function is_balanced_helper to check if the tree is balanced; it returns TRUE if all nodes have valid heights and FALSE if any node returns $-1$, indicating an imbalance.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s implement the algorithm as discussed above: