Description: Given a tree we have to check if children sum property is satisfied. Children sum property means that the value of every node is the sum of values of left and right child. The value of an empty/null left or right child is considered to be 0.

Example:

Tree below satisfies sum property because

3+5==8

and 1+2==3

Hence, value of every node is sum of values of left and right children.

Algorithm and Implementation:

A tree or part of a tree satisfies children sum property only if the root element satisfies the property, along with left and right subtrees. This can be converted into a recursive definition.

/*The following function checks if children sum property isn satisified*/

int checkprop(struct node *node)

{

int leftval= 0,  rightval= 0;

if(node == NULL || (node->left == NULL && node->right == NULL))

return 1;

else

{

if(node->left != NULL)

leftval= node->left->data;

if(node->right != NULL)

rightval= node->right->data;

if((node->data == leftval + rightval)&&  checkprop(node->left) &&  checkprop(node->right))

return 1;

else

return 0;

}

}

Time Complexity:

O(n), where 'n' is the number of nodes in the tree.

Go to top