Manas Sinha

Developer | Designer

Manas Sinha

Developer | Designer

## By Manas | 28 September 2021 | 2 mins read

## BALANCED TREES AND

iNTRODUCTION TO SELF BALANCING TREES

Balance Factor | Why do we need SBT?

To start this article I would like to remind you of the reason we introduced tree data structures in the first place? Along with the hierarchy, trees help us to do a certain operation like search, insert, etc on a set of values in O(log N) time which might otherwise take O(n) time if we were to use some linear data structure like arrays or linked list. With this in mind, look at the below three images:

- The first one is a simple binary tree. Think of searching for a value in this tree. Since there is no order, we will have to visit all the nodes. Hence, it will take O(n) time. This doesn’t seem to be helping us. So, we came up with another structure, the Binary search tree.
- The second one is a binary search tree. This tree has the property that the values in the left subtree are less than the root node, and the values of the right subtree are greater than the root node. And this property holds for all the subtrees of this tree. Using this tree we can search a value in O(log N) time. But now look at the third image. It is also a BST.
- The third one is a skewed BST. This looks similar to the linked list. If we try to find a value in this tree, the complexity will again be O(n). This is the worst case of a BST. The skewed BST. The evil doesn’t seem to stay quiet, does it?. What do we do now? We are again at square one. Or are we? Try to think about how can you solve this problem? The answer is to balance this tree like this:

Now I think you must be getting an idea of why we are even bothering learning a new data structure which is the Self-balancing tree. If you are not, I suggest you read the above four paragraphs again. Because before learning anything, you must first know why? Well.. it’s true in most cases, sometimes you have to take a leap of faith.
Let’s now see what the technical definition of ‘Balanced Tree’ is.

## 0. WHAT IS A BALANCED TREE?

- balance factor = height(left subtree) – height(right subtree)

- | balance factor | <= 1

## 1. FIND IF A TREE IS BALANCED OR NOT.

Check if a tree is balanced or not programmatically:

```
/* Author: The Binary Realm */
/* CPP function to check if
a tree is height-balanced or not*/
bool treeIsBanaced(TreeNode* root, int* curr_height){
/* If the root is null the height is -1*/
if(root == NULL){
*curr_height = -1;
return true;
}
int left_height = -1, right_height = -1;
/* check if the left and right subtrees
are balanced */
bool left_balanced = treeIsBanaced(root->left, &left_height);
bool right_balanced = treeIsBanaced(root->right, &right_height);
/* height of the current node */
*curr_height = max(left_height, right_height) + 1;
int balance_factor = left_height - right_height;
/* checking all the three conditions */
return (abs(balance_factor) <= 1) && left_balanced && right_balanced;
}
```

Pingback: AVL Trees | Self-Balancing Trees | Everything You need To know - TheBinaryRealm