All About Balanced Binary Tree

All About Balanced Binary Tree

4 mins read4.1K Views Comment
clickHere
Updated on May 1, 2023 17:59 IST

Balanced binary search trees like AVL tree, m-tree, and Red-Black Tree are way more efficient than unbalanced binary trees. Hence, these efficient trees result in more efficient time complexities and can be used for data organization in the memory.

2022_12_MicrosoftTeams-image-98-1.jpg

In this article, we will discuss a balanced binary tree, the conditions for a balanced binary tree, a self-balancing binary tree, and how to check whether a binary tree is balanced or not.

Table of Contents

What is a Binary Tree?

A binary tree is an important data structure in computer programming as it can organize data efficiently. Binary tree in data structure has numerous types, and one of its most important and widely used types is the balanced binary tree. A binary tree has either zero, one, or two child nodes but not more than two. Other types of binary trees include a Complete binary tree, full binary tree, skewed binary tree (left-skewed tree, right-skewed tree), and degenerate binary tree. 

What is a Balanced Binary Tree?

A balanced binary tree or height-balanced binary tree is such a tree whose left and right subtrees' heights differ by not more than 1, which means the height difference could be -1, 0, and 1. A balanced binary tree is also known as a height-balanced tree.

Necessary conditions for a balanced binary tree:

  1. The height difference should not be more than 1.
  2. The Left sub-tree should be balanced.
  3. The right sub-tree should be balanced.

The height difference of a tree is calculated as |Left subtree| – |Right subtree| or |Right subtree| – |Left subtree|. The difference should not be more than 1. 

Example of Balanced Binary Tree

Balanced Binary Tree
Balanced Binary Tree 2

Self-balancing Tree

In data structure and programming, we mainly discuss two self-balancing binary search trees, which are as follows:

  1. AVL tree
  2. Red-Black Tree

AVL Tree:

If any binary tree, which is balanced means whose height difference or balance factor is 1, then it is known as an AVL tree. AVL trees are self-balancing binary search trees. AVL trees left sub-tree and right sub-tree to have a height difference at most 1. 

If there is any disturbance in the balancing factor or the height difference between the left sub-tree and the right sub-tree is more than one, then we must balance the binary tree. balancing of the binary tree can be done using:

  1. Left Rotation
  2. Right Rotation
  3. Left-Right rotation
  4. Right-Left rotation

Red-Black Tree:

A red-black tree is a binary search tree with the property of a self-balancing binary search tree. For balancing the height of the tree, it uses two colours, red and black, in order to ensure that the tree is balanced even after multiple insertions and deletion operations. Being a variant of a binary search tree Red Black tree also has at most two children, which means that a node either can have zero, one, or two children but not more than two. 

Here are some properties of the Red Black Tree which must be considered whenever designing a Red-Black tree, so the properties are as follows:

  1. The red-black tree is a self-balancing binary search tree. 
  2. The root node should be Black in color.
  3. Every node would have either red/black color.
  4. Every leaf node which is NIL would be in Black color.
  5. If the node is in Red color, then its children must be in Black color.
  6. Every path from a node to any of its descendant NIL nodes has the same number of black trees.

Explore Free Online Courses with Certificates

How to check whether a binary tree is balanced or not?

Here are a few conditions; by checking them, we can ensure whether the given tree is balanced or not. 

  1. The height difference or balance factor should be at most one, not more than that. 
  2. The left sub-tree should be balanced
  3. The right sub-tree should be balanced. 

The pseudo-code for checking a balanced binary tree is as follows:

  • If node == null, then return 0
  • Check the left sub-tree. If not balanced → return -1
  • Check the right sub-tree. If not balanced → return -1
  • The absolute difference between heights of left and right subtrees. If it is greater than 1 → return -1.
  • If the tree is balanced → return height. 
Tree Data Structure: Types, Properties, and Applications
Tree Data Structure: Types, Properties, and Applications
The purpose of this blog is to explain you the what is tree data structure. We have also covered its types, properties and applications. Let’s understand! A data structure is...read more
Understanding Dijkstra’s Algorithm
Understanding Dijkstra’s Algorithm
Dijkstra’s algorithm or Dijkstra’s shortest path algorithm or single source shortest path algorithm is used in identifying the shortest path from starting node to a destination node in a weighted...read more
All About Kruskal’s Algorithm
All About Kruskal’s Algorithm
Kruskal’s algorithm is based on a greedy approach, whose goal is to find the shortest path in a graph with a minimum cost.

Implementation


 
int main() {
int height = 0;
struct node *root = newNode(A);
root- > left = newNode(B);
root- > right = newNode(C);
root- > left- > left = newNode(D);
root- > left- > right = newNode(E);
if (checkHeBal(root, &height))
printf("The tree is balanced");
else
printf("The tree is not balanced");
}
#include < stdio.h >
#include < stdlib.h >
#define bool int
struct node {
int item;
struct node *left;
struct node *right;
};
struct node *newNode(int item) {
struct node *node = (struct node *)malloc(sizeof(struct node));
node- > item = item;
node- > left = NULL;
node- > right = NULL;
return (node);
}
bool checkHeBal(struct node *root, int *height) {
int leftHe= 0, rightHe= 0;
int l = 0, r = 0;
if (root == NULL) {
*height = 0;
return 1;
}
l = checkHeBal(root- > left, &leftHe);
r = checkHeBal(root- > right, &rightHe);
*height = (leftHe > rightHe ? leftHe: rightHe) + 1;
if ((leftHe - rightHe > = 2) || (rightHe - leftHe > = 2))
return 0;
else
return l && r;
}
Copy code

 

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio