Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Binary Tree?
3.
What is a Balanced Binary Tree?
4.
Conditions of Balanced Binary Tree
4.1.
1. Difference between the left and right subtree depth
4.2.
2. Left Subtree should be balanced
4.3.
3. Right Subtree should be balanced
5.
Example of Balanced Binary Tree
6.
Implementation of Balanced Binary Tree
6.1.
C
6.2.
C++
6.3.
Java
6.4.
Python
6.5.
Javascript
6.6.
C#
7.
Applications of Balanced Binary Tree
8.
Advantages of Balanced Binary Tree
9.
Frequently Asked Questions
9.1.
What is the K balanced binary tree?
9.2.
What is the difference between a complete and balanced binary tree?
9.3.
What is the balanced binary tree formula?
9.4.
How many nodes are in a balanced binary tree?
10.
Conclusion
Last Updated: May 7, 2024
Medium

Balanced Binary Tree

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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.

Balanced Binary Tree

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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):

unbalanced binary tree - representation

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:

balanced binary tree - representation

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++PythonJava 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;
}

C++

// 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;
}


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))
cout << "Given Binary Tree is balanced";
else
cout << "Given Binary Tree is not balanced";
}

Java

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");
}
}

Python

class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None


def create_node(data):
return Node(data)


def check_height_balance(root, height):
if root is None:
height[0] = 0
return True
left_height, right_height = [0], [0]
l = check_height_balance(root.left, left_height)
r = check_height_balance(root.right, right_height)
height[0] = max(left_height[0], right_height[0]) + 1
if abs(left_height[0] - right_height[0]) >= 2:
return False
else:
return l and r


# Creating root with createNode() function
root = create_node(15)
root.left = create_node(10)
root.right = create_node(20)
root.left.left = create_node(5)
root.left.right = create_node(40)

# 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")

Javascript

class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}

function createNode(data) {
return new Node(data);
}

function checkHeightBalance(root, height) {
if (root === null) {
height[0] = 0;
return true;
}
const leftHeight = [0];
const rightHeight = [0];
const l = checkHeightBalance(root.left, leftHeight);
const 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;
}

// Creating root with createNode() function
const 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
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");

C#

using System;

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

implementation of balanced binary tree - 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:

 

You can refer to our guided paths on the Code360. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. 

Also, check out Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Happy Learning!

Live masterclass