## 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);

}

}

__: O(n*n)__

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

You can do it in O(n) also,

ReplyDeleteuse recursion, and on back-tracing update the data's of parents node depending how child node have updated their values..!!

like you have done in next problem, you just have to do the same, but instant of checking the condition before recursion, you have to apply child sum pro. after recursion,

Delete