Answer:
See explaination
Step-by-step explanation:
/* Program to check if a given Binary Tree is balanced like a Red-Black Tree */
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int key;
struct Node *left, *right;
};
/* utility that allocates a new Node with the given key */
struct Node* newNode(int key)
{
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->key = key;
node->left = node->right = NULL;
return (node);
}
int max(int a,int b)
{
if(a>b)return a;
else return b;
}
int min(int a,int b)
{
if(a>b)return b;
else return a;
}
// Returns returns tree if the Binary tree is balanced like a Red-Black
// tree. This function also sets value in maxh and minh (passed by
// reference). maxh and minh are set as maximum and minimum heights of root.
int isBalancedUtil(struct Node *root, int maxh, int minh)
{
// Base case
if (root == NULL)
{
maxh = minh = 0;
return 1;
}
int lmxh, lmnh; // To store max and min heights of left subtree
int rmxh, rmnh; // To store max and min heights of right subtree
// Check if left subtree is balanced, also set lmxh and lmnh
if (isBalancedUtil(root->left, lmxh, lmnh) == 0)
return 0;
// Check if right subtree is balanced, also set rmxh and rmnh
if (isBalancedUtil(root->right, rmxh, rmnh) == 0)
return 0;
// Set the max and min heights of this node for the parent call
maxh = max(lmxh, rmxh) + 1;
minh = min(lmnh, rmnh) + 1;
// See if this node is balanced
if (maxh <= 2*minh)
return 1;
return 1;
}
// A wrapper over isBalancedUtil()
int isBalanced(struct Node *root)
{
int maxh, minh;
return isBalancedUtil(root, maxh, minh);
}
/* Driver program to test above functions*/
int main()
{
struct Node * root = newNode(10);
root->left = newNode(5);
root->right = newNode(100);
root->right->left = newNode(50);
root->right->right = newNode(150);
root->right->left->left = newNode(40);
isBalanced(root)? printf( "Balanced RBT" ): printf( "Not Balanced Tree");
return 0;
}