We define a mobile tree as a binary tree with nodes of the following type: struc

Question

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

Here is the code for the function isInBalance() . It makes use of another function weight() to get the weight of subtree. Please don't forget to rate the answer if it helped. Thank you very much.

//function to calculate the weight of a subtree rooted at root
//weight is the sum of weight in its node, left and right subtrees
int weight(Node *root)
{
if(root == NULL)
return 0;

int weight = root->weight;
weight += weight(root->left);
weight += weight(root->right);
return weight;
}

bool isInBalance(Node *root)
{
if(root == NULL) //empty tree is balanced
return true;

//if left subtree weight is same as right subtree and left is balanced and right is also balanced
if(weight(root->left) == weight(root->right) && isInBalance(root->left) && isInBalance(root->right))
return true;
else
return false;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.