Check for Children Sum Property in a Binary Tree
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
if(root == NULL)
if(root->left == NULL && root->right == NULL)
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.
Time Complexity : O(n), we are doing a complete traversal of the tree.
Check out the extension of this problem "Convert arbitrary binary tree to a tree that holds Children Sum Property".