## Check for Children Sum Property in a Binary Tree

**Problem Statement**Given a binary tree, write a function that returns true if the tree satisfies below 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

**Solution**
int checkCSP(node * root) {

if(root == NULL)

return 1;

if(root->left == NULL && root->right == NULL)

return 1;

int sum = 0;

if(root->left != NULL)

sum += root->left->data;

if(root->right != NULL)

sum += root->right->data;

return (root->data == sum) && checkCSP(root->left) && checkCSP(root->right);

}

//If you have a different approach in mind, please share it in comments section for our readers.

if(root == NULL)

return 1;

if(root->left == NULL && root->right == NULL)

return 1;

int sum = 0;

if(root->left != NULL)

sum += root->left->data;

if(root->right != NULL)

sum += root->right->data;

return (root->data == sum) && checkCSP(root->left) && checkCSP(root->right);

}

//If you have a different approach in mind, please share it in comments section for our readers.

__: O(n), we are doing a complete traversal of the tree.__

**Time Complexity**Check out the extension of this problem "Convert arbitrary binary tree to a tree that holds Children Sum Property".

## No comments:

## Post a Comment