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.

If video does not load, Click here

Tree below satisfies sum property because


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;



   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;


     return 0;



Time Complexity:


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

Go to top