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