Balanced Binary Tree

A balanced binary tree is just a random nod-based tree with a rule of keeping its height minimum in size to maintain various operations such as insertions, deletions and several others. A balanced binary tree turns out to be one in which all the leaf nodes are at a considerable distance from the base or root nod compared to any other node in the tree. A significant amount of work is supposed to be done to keep them balanced and maintained. Balanced binary trees are also technically called height-balanced binary trees. They are generally denoted by the symbol HB(k), where we know that k stands for the difference between both the left and rt subtrees. Suppose we have a tree that contains the value of k as 0; then, the tree would be considered a fully balanced binary tree

 in that situation. 

To check whether the tree's height is balanced, we have first to get the difference between the two left and rt subtrees, and if the difference between the two is not more than one, then it will return the value true otherwise, false.

The time complexity of the balanced binary tree is known to be O(n2), and the auxiliary complexity of the same is known to be O(n) since it has recursions.

Conditions

There are some well-defined conditions which we have to follow to keep the tree well-maintained. They are as follows: -

• The subtree on the rt is supposed to be balanced.
• The subtree on the left is supposed to be balanced.
• The difference between both the subtrees is not more than one.

Implementation

This section of the article will give examples of the implementation and working of the balanced binary tree to help you understand the concept better.

// Checking if a binary tree is a height-balanced in C++

Example 1)

#include 
using namespace std;


#define bool int


Class N {
   public:
  int item;
  nod *lft;
  nod *rt;
};


// Create anew nod
nod *newNod(int item) {
  nod *Nod = new nod();
  Nod->item = item;
  Nod->lft = NILL;
  Nod->rt = NILL;


  return (Nod);
}


// Check height balance
bool checkHeightBalance(nod *root, int *height) {
  // Check for emptiness
  int lftHeight = 0, rtHeight = 0;


  int l = 0, r = 0;


  if (root == NILL) {
    *height = 0;
    return 1;
  }


  l = checkHeightBalance(root->lft, &lftHeight);
  r = checkHeightBalance(root->rt, &rtHeight);


  *height = (lftHeight > rtHeight ? lftHeight : rtHeight) + 1;


  if (std::abs(lftHeight - rtHeight >= 2))
    return 0;


  else
    return l && r;
}


int main() {
  int height = 0;


  nod *root = newNod(1);
  root->lft = newNod(2);
  root->rt = newNod(3);
  root->lft->lft = newNod(4);
  root->lft->rt = newNod(5);


  if (checkHeightBalance(root, &height))
    cout << "The tree is balanced";
  else
    cout << "The tree is not balanced";
}

Output:

Example 2)

#include <bits/stdc++.h>
using namespace std;


/* A binary tree nod has info,
pointer to lft child and
a pointer to the rt nod */
class N {
public:
	int info;
	Nod* lft;
	Nod* rt;
	Nod(int d)
	{
		int info = d;
		lft = rt = NILL;
	}
};


// Function to calculate the height of a tree
int height(Nod* nod)
{
	// base case tree is empty
	if (nod == NILL)
		return 0;


	// If a tree is not empty, then
	// height = 1 + max of lft height
	// and rt heights
	return 1 + max(height(nod->lft), height(nod->rt));
}


// Returns true if binary tree
// with root as root is height-balanced
bool isBalanced(Nod* root)
{
	int lh; // for the height of lft subtree
	int rh; // for the height of rt subtree


	// If a tree is empty, then return true
	if (root == NILL)
		return 1;


	// Get the height of lft and rt subtrees
	lh = height(root->lft);
	rh = height(root->rt);


	if (abs(lh - rh) <= 1 && isBalanced(root->lft)
		&& isBalanced(root->rt))
		return 1;


	// If we reach here, then the tree is not height-balanced
	return 0;
}


// Driver code
int main()
{
	Nod* root = new Nod(1);
	root->lft = new Nod(2);
	root->rt = new Nod(3);
	root->lft->lft = new Nod(4);
	root->lft->rt = new Nod(5);
	root->lft->lft->lft = new Nod(8);


	if (isBalanced(root))
		cout << "Tree is balanced";
	else
		cout << "Tree is not balanced";
	return 0;
}

Output: