GeeksforGeeks- Arbitrary Binary Tree to a tree that holds Children Sum Property problem : C code

Convert an arbitrary binary tree to a tree that hold children sum property

Problem Statement

Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node (You cannot change structure of tree and cannot decrement value of any node) 

Children Sum Property - For every node, data value must be equal to sum of data values in left and right children. Consider data value as 0 for NULL children.

Algorithm

Traverse given tree in post order to convert it, first change left and right children of node to hold the CSP property and then change the parent node
Let difference between node’s data and children sum be diff.

     diff = sum of node’s children  - node’s data

If diff is 0 then you need to do nothing
If diff > 0 then you need to increment the node’s data by diff.
If diff < 0 then you need to increment one child’s data. But we have a choice we can increment either left child or right child, so I choose left child but this changes the children sub property for the left subtree so that also need to be fixed. So we recursively increment the left child. If left child is empty then we recursively call increment() for right child.

Solution

void convertTree(node *root)
{
    if(root == NULL)
        return;
    if(root->left == NULL && root->right == NULL)
        return;
   
    convertTree(root->left);
    convertTree(root->right);
       
    int sum = 0, diff;
    if(root->left != NULL)
        sum += root->left->data;
    if(root->right != NULL)
        sum += root->right->data;
   
    diff = sum - root->data;
   
    if(diff == 0)
        return;
   
    else if(diff > 0)
        root->data += diff;
   
    else
        increment(root, -diff);
}
   
void increment(node *root, int value)
{

    if(root->left != NULL) {
        root->left += value;
        increment(root->left, value);
    }
    else if (root->right != NULL) {
        root->right += value;
        increment(root->right, value);
    }
}

Time Complexity : O(n*n)


// If you find this blog somewhat helpful, please share it.......&.......Keep visiting..:)