Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
The tree is a non-linear hierarchical data structure where the elements are stored in a non-sequential manner that makes operations such as insertion and deletion faster than linear data structures such as Arrays, Linked Lists, stacks, and queues. There are different types of trees like Binary Trees, Binary Search Trees, AVL Trees, B - Tree, etc.
What is Binary Tree?
The binary tree is a non-linear data structure based on hierarchy, which is one of the types of tree data structures. In a binary tree, one parent node can have at most two children, where every node contains three items: data, the address of the left child, and the right child.
What is a Balanced Binary Tree?
A balanced Binary Tree is a type of binary tree where the height of the left and right subtree of each node in the binary tree should be 0 or 1. The structure of the balanced binary tree is the same as the binary tree structure.
Conditions of Balanced Binary Tree
The condition of Balanced Binary tree are:-
1. Difference between the left and right subtree depth
In a balanced binary tree, there is a term known as ‘depth factor’, which is supposed to find each node in the tree by which it can be determined if the binary tree is balanced or not.
df = | height of left child - height of right child |
Where df stands for depth factor, and its value should be 0 or 1 for the criteria of a balanced binary tree.
2. Left Subtree should be balanced
The left subtree of a particular node in the binary tree should be balanced in order to call it a balanced binary tree.
3. Right Subtree should be balanced
The right subtree of a particular node in the binary tree should be balanced in order to call it a balanced binary tree.
Example of Balanced Binary Tree
In this example, we will understand the concept of a balanced binary tree with the help of representations. Here is the representation of a binary tree that is not balanced (or unbalanced):
In the above image, the df (depth factor) of all the nodes except the root node is either 0 or 1. But the depth factor of the root node is 2. So, even if a single node does not meet the criteria for a balanced binary tree, then the binary tree will known as the unbalanced binary tree.
Here is the representation of a binary tree that is balanced:
In the above binary tree, the depth factor for each node is either 0 or 1. So, the binary tree is balanced, which is also known as a balanced binary tree.
Implementation of Balanced Binary Tree
In this section, we will check if the given binary tree is balanced or not with the C++, Python, Java and C programming language:
C
C++
Java
Python
Javascript
C#
C
#include <stdio.h> #include <stdlib.h>
// Creating structure for nodes struct node { int data; struct node *left; struct node *right; };
/* Function to create a node for given data with left and right pointer to nullptr. */ struct node *createNode(int data) { struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = node->right = NULL; return node; }
// Creating a function to check height balance int checkHeightBalance(struct node *root, int *height) { // Creating two variables for left and right subtree heights int leftHeight = 0, rightHeight = 0; int l = 0, r = 0; // If the root element is not present if (!root) { *height = 0; return 1; } // Getting height for l l = checkHeightBalance(root->left, &leftHeight); // Getting height for r r = checkHeightBalance(root->right, &rightHeight); *height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; if (abs(leftHeight - rightHeight >= 2)) return 0; else return l && r; }
int main() { // Creating root with createNode() function struct node *root = createNode(15); root->left = createNode(10); root->right = createNode(20); root->left->left = createNode(5); root->left->right = createNode(40); // Initializing height variable with 0 int height = 0; /* If the binary tree is balanced with the help of root and created variable height */ if (checkHeightBalance(root, &height)) printf("Given Binary Tree is balanced"); else printf("Given Binary Tree is not balanced"); return 0; }
// Importing necessary CPP libraries #include <bits/stdc++.h> using namespace std;
// Creating structure for nodes struct node { int data; struct node *left; struct node *right; };
/* Function to create a node for given data with left and right pointer to nullptr. */ struct node *createNode(int data) { struct node *node = (struct node *) malloc(sizeof(struct node)); node->data = data; node->left = node->right = nullptr; return node; }
// Creating a function to check height balance bool checkHeightBalance(node *root, int *height) {
// Creating two variables for left and right subtree heights int leftHeight = 0, rightHeight = 0;
int l = 0, r = 0;
// If the root element is not present if (!root) { *height = 0; return 1; }
// Getting height for l l = checkHeightBalance(root->left, &leftHeight);
// Getting height for r r = checkHeightBalance(root->right, &rightHeight); *height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; if (abs(leftHeight - rightHeight >= 2)) return 0; else return l && r; }
// Initializing height variable with 0 int height = 0;
/* If the binary tree is balanced with the help of root and created variable height */ if(checkHeightBalance(root, &height)) cout << "Given Binary Tree is balanced"; else cout << "Given Binary Tree is not balanced"; }
You can also try this code with Online C++ Compiler
class Main { // Creating structure for nodes static class Node { int data; Node left, right;
Node(int data) { this.data = data; left = right = null; } }
static Node createNode(int data) { return new Node(data); }
// Creating a function to check height balance static boolean checkHeightBalance(Node root, int[] height) { if (root == null) { height[0] = 0; return true; } int[] leftHeight = new int[1]; int[] rightHeight = new int[1]; boolean l = checkHeightBalance(root.left, leftHeight); boolean r = checkHeightBalance(root.right, rightHeight); height[0] = Math.max(leftHeight[0], rightHeight[0]) + 1; if (Math.abs(leftHeight[0] - rightHeight[0]) >= 2) return false; else return l && r; }
public static void main(String[] args) { // Creating root with createNode() function Node root = createNode(15); root.left = createNode(10); root.right = createNode(20); root.left.left = createNode(5); root.left.right = createNode(40); // Initializing height variable with 0 int[] height = new int[1]; /* If the binary tree is balanced with the help of root and created variable height */ if (checkHeightBalance(root, height)) System.out.println("Given Binary Tree is balanced"); else System.out.println("Given Binary Tree is not balanced"); } }
You can also try this code with Online Java Compiler
# Initializing height variable with 0 height = [0]
# If the binary tree is balanced with the help of root and created variable height if check_height_balance(root, height): print("Given Binary Tree is balanced") else: print("Given Binary Tree is not balanced")
You can also try this code with Online Python Compiler
// Initializing height variable with 0 const height = [0];
/* If the binary tree is balanced with the help of root and created variable height */ if (checkHeightBalance(root, height)) console.log("Given Binary Tree is balanced"); else console.log("Given Binary Tree is not balanced");
You can also try this code with Online Javascript Compiler
class MainClass { // Creating structure for nodes class Node { public int data; public Node left, right;
public Node(int data) { this.data = data; left = right = null; } }
static Node createNode(int data) { return new Node(data); }
// Creating a function to check height balance static bool checkHeightBalance(Node root, ref int height) { if (root == null) { height = 0; return true; } int leftHeight = 0, rightHeight = 0; bool l = checkHeightBalance(root.left, ref leftHeight); bool r = checkHeightBalance(root.right, ref rightHeight); height = Math.Max(leftHeight, rightHeight) + 1; if (Math.Abs(leftHeight - rightHeight) >= 2) return false; else return l && r; }
public static void Main(string[] args) { // Creating root with createNode() function Node root = createNode(15); root.left = createNode(10); root.right = createNode(20); root.left.left = createNode(5); root.left.right = createNode(40); // Initializing height variable with 0 int height = 0; /* If the binary tree is balanced with the help of root and created variable height */ if (checkHeightBalance(root, ref height)) Console.WriteLine("Given Binary Tree is balanced"); else Console.WriteLine("Given Binary Tree is not balanced"); } }
Output
Explanation
Here is the explanation for the above code:
The struct keyword is used to create the tree data structure.
The ‘createNode’ function is created for initialization of the data value, pointer of left and right to given data, and nullptr, respectively.
The ‘checkHeightBalance’ function is created to check if the tree is balanced or not.
Then, the nodes of the binary tree are created using the ‘createNode’ function, and the ‘checkHeightBalance’ function is used to print if the given binary tree is balanced or not.
Applications of Balanced Binary Tree
Here are some of the applications of a balanced binary tree, as follows:
AVL Tree: A balanced Binary Tree can be used for creating AVL trees as an AVL tree also maintains the balance factor, which is the same as the depth factor.
Balanced Binary Search Tree: Balanced Binary Tree can be used for creating a balanced binary search tree that maintains the depth factor in the binary search tree to make the operations more optimal.
Needs Less Complexity: Balanced Binary Trees can be used where the number of operations on the tree is greater. So the complexity can be reduced by using a balanced binary tree.
Advantages of Balanced Binary Tree
Here are some of the advantages of a balanced binary tree, as follows:
Time Complexity for operations like searching, insertions, and deletions on the binary tree can be reduced.
Balanced Binary Search Trees can be better used for accessing the elements instead of binary heaps.
The overall height of the binary tree can be reduced if the binary tree is balanced.
A balanced Binary Search Tree can be helpful when the ordering of data should be maintained.
Frequently Asked Questions
What is the K balanced binary tree?
A K-balanced binary tree is a binary tree where the height difference between the left and right subtrees of any node is at most K. This ensures that the tree remains balanced, preventing skewed structures and maintaining efficient operations like search and insertion.
What is the difference between a complete and balanced binary tree?
A complete binary tree is one where all levels are completely filled except possibly for the last level, which is filled from left to right. In contrast, a balanced binary tree ensures that the height difference between the left and right subtrees of any node is minimal, optimizing performance while accommodating dynamic data.
What is the balanced binary tree formula?
The balanced binary tree formula is based on ensuring that the height difference between the left and right subtrees of any node is within a certain threshold, typically 1. This formula involves maintaining balance during insertion and deletion operations to prevent the tree from becoming skewed.
How many nodes are in a balanced binary tree?
The number of nodes in a balanced binary tree can vary depending on its height and structure. However, in general, for a balanced binary tree with height 'h', the maximum number of nodes is 2^(h+1) - 1, where 'h' is the height of the tree.
Conclusion
The balanced binary tree is a type of binary tree that is basically used to reduce the time complexity where the depth factor is determined for each node in the tree. The depth factor of each node in the binary tree should always be 0 or 1 to meet the criteria of a balanced binary tree.
In this article, we discussed firstly binary tree, then balanced binary tree with the example, the implementation, and its application. Here are more articles that are recommended to read: