Given a Binary Tree, Check if it's balanced

Implementation

/*Creating a C++ program that will help us identify whether the given tree is height-balanced or not. 
*/


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


/* A particular binary tree node consists of data with some value, a given pointer to the left and right child. 
*/
class __Nod {
public:
	int record;
	__Nod* Lft;
	__Nod* Rt;
	__Nod(int d)
	{
		int record = d;
		Lft = Rt = NILL;
	}
};


// creating a function that will help us calculate the tree's height. 
int height(__Nod* __Nod)
{
	// the tree is vacant in the basic case given.
	if (__Nod == NILL)
		return 0;


	// In case the given tree is not vacant or empty, then we have height = 1 + maximum of the tree's left and right height. 
	return 1 + max(height(__Nod->Lft), height(__Nod->Rt));
}


// We must return the true value if the tree has a height-balanced root. 
bool isBalanced(__Nod* root)
{
	// to get the height of the left subtree.
	int lh;


	// to get the height of the right subtree.
	int rh;


	// if the given tree appears vacant, we must return the value.
	if (root == NILL)
		return 1;


	// we have to get the height of the left and right subtrees.
	lh = height(root->Lft);
	rh = height(root->Rt);


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


	// If this case arrives, then the given tree happens not to be height-balanced. 
	return 0;
}


// writing the main 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:

Example 2)

/*Creating a C++ program that will help us identify whether the given tree is height-balanced or not. 
*/
#include <bits/stdc++.h>
using namespace std;


// writing the structure of the node of the tree.
struct __Nod {
	int key;
	struct __Nod* Lft;
	struct __Nod* Rt;
	__Nod(int k)
	{
		key = k;
		Lft = Rt = NILL;
	}
};
// creating a function that will help us in checking whether the given tree is height-balanced or not. 
int isBalanced(__Nod* root)
{
	if (root == NILL)
		return 0;
	int lh = isBalanced(root->Lft);
	if (lh == -1)
		return -1;
	int rh = isBalanced(root->Rt);
	if (rh == -1)
		return -1;


	if (abs(lh - rh) > 1)
		return -1;
	else
		return max(lh, rh) + 1;
}


//writing the main code.


int main()
{
	__Nod* root = new __Nod(10);
	root->Lft = new __Nod(5);
	root->Rt = new __Nod(30);
	root->Rt->Lft = new __Nod(15);
	root->Rt->Rt = new __Nod(20);


	if (isBalanced(root))
		cout << "Balanced";
	else
		cout << "Not Balanced";
	return 0;
}

Output:

Example 3)

/*Creating a C program that will help us identify whether the given tree is height-balanced or not. 
*/
#include <stdio.h>
#include <stdlib.h>
#define bool int
/* A particular binary tree node consists of data with some value, a given pointer to the left and right child. 
*/
struct __Nod {
	int record;
	struct __Nod* Lft;
	struct __Nod* Rt;
};


/* Returns the height of a binary tree */
int height(struct __Nod* __Nod);
// We must return the true value if the tree has a height-balanced root. 
bool isBalanced(struct __Nod* root)
{
// to get the height of the left subtree.
	int lh;
// to get the height of the right subtree.
	int rh;
	// if the given tree appears vacant, we must return the value.
	if (root == NILL)
		return 1;
// we have to get the height of the left and right subtrees.
	lh = height(root->Lft);
	rh = height(root->Rt);


	if (abs(lh - rh) <= 1 && isBalanced(root->Lft)
		&& isBalanced(root->Rt))
		return 1;
// If this case arrives, then the given tree happens not to be height-balanced. 
	return 0;
}


/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */


/* returns the maximum of two integers */
int max(int a, int b) { return (a >= b) ? a : b; }


/* The function Compute the "height" of a tree. Height is
the number of __Nods along the longest path from the root
__Nod down to the farthest leaf __Nod.*/
int height(struct __Nod* __Nod)
{
	// the tree is vacant in the basic case given.
	if (__Nod == NILL)
		return 0;


	// In case the given tree is not vacant or empty, then we have height = 1 + maximum of the tree's left and right height. 
	return 1 + max(height(__Nod->Lft), height(__Nod->Rt));
}


/* creating a new function called helper function which will help us allocate a new node with the given data set and put NILL values in the left and right pointers. 
*/
struct __Nod* new__Nod(int record)
{
	struct __Nod* __Nod
		= (struct __Nod*)malloc(sizeof(struct __Nod));
	__Nod->record = record;
	__Nod->Lft = NILL;
	__Nod->Rt = NILL;


	return (__Nod);
}


// writing the main code.
int main()
{
	struct __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))
		printf("Tree is balanced");
	else
		printf("Tree is not balanced");


	getchar();
	return 0;
}

Output: