You are given a binary tree, you have to check if tree satisfies the property of children sum. This property says that for each node sum of its left and right children should be equal to node value.
Solution:
1)Traverse the given binary tree (recursively)
2) For each node check if the node and both its children satisfy the Children Sum Property.
3) If so then return true else return false.
struct mynode { int data; struct mynode* left; struct mynode* right; }; /* returns 1 if children sum property holds */ int checkChildrenSum(struct mynode* mynode) { int leftValue,rightValue; leftValue=0;rightValue=0; if(mynode == NULL || (mynode->left == NULL && mynode->right == NULL)) return 1; else { if(mynode->left != NULL) leftValue = mynode->left->data; if(mynode->right != NULL) rightValue = mynode->right->data; if((mynode->data == leftValue + rightValue) && checkChildrenSum(mynode->left) && checkChildrenSum(mynode->right)) return 1; else return 0; } }
Complexity: O(N)
bool checkChildrenSumProperty(node *root) {
if (!root)
return true;
else {
int vl = root->left ? root->left->val : 0;
int vr = root->right ? root->right->val : 0;
if (root->val != vl+vr)
return false;
else {
return checkChildrenSumProperty(root->left) && checkChildrenSumProperty(root->right);
}
}
}