Friday, 1 June 2012

Check for Children Sum Property in a Binary Tree : C code

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


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. 

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".

No comments:

Post a Comment