Could anyone provide the function taking (Node* root) as a parameter that would
ID: 3847713 • Letter: C
Question
Could anyone provide the function taking (Node* root) as a parameter that would make this particular tree balanced if it was not?
We define a mobile tree as a binary tree with nodes of the following type: struct Node int weight the weight of this node itself Node* left; Node right Define the weight of a mobile tree to be the sum of the weights of all the nodes in the tree. The empty tree therefore has a weight of zero.) We say that a mobile tree is in balance if either: it is empty, or if the weights of its left and right subtrees are equal, and each of those subtrees is itself in balance. This mobile tree, for example, is in balance:Explanation / Answer
//calculates the weight of node
int getWeight(Node *root)
{
if(root == NULL)
return 0;
int weight = root->weight + getWeight(root->left) + getWeight(root->right);
return weight;
}
bool isBalanced(Node *root)
{
//empty tree is balanced
if(root == NULL)
return true;
//balanced if left and right subtree have same weight and are balanced
if(getWeight(root->left) == getWeight(root->right) && isBalanced(root->left) && isBalanced(root->right))
return true;
else
return false;
}
Please rate the answer if it helped. Thanks.