Program to Check Children Sum Property in a Binary Tree

  • Write a C program to check if a binary tree satisfy Children Sum Property.

Given a binary tree We have to check whether given binary tree satisfy children sum property. We will traverse each node of binary tree and check whether children sum property holds true for each node or not.

Children Sum Property of Binary Tree
If the value of every node of a binary tree is equal to the sum of it's left and right child node then binary tree satisfies child sum property.
  • A sub tree rooted at a leaf node satisfies children sum property because leaf nodes don't have any child nodes.
  • An Empty tree satisfies Children sum property.
Algorithm to check Children Sum property of a binary tree
Let "node" be the pointer to any node of binary tree.
  • If node is NULL, then return true.
  • If node is leaf node, then return true.
  • If node's value is equal to sum of left and right child nodes and left and right sub trees also satisfies Children sum property. Then sub tree rooted at node satisfies children sum property.
Time Complexity : O(n), we are traversing binary tree only once.

C program to check children sum property of binary tree

#include <stdio.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns a binary tree which 
satisfy children sum property  
            10
           / \
         4    6
        / \  / \
       2  2 3  3
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(10);

    root->left = getNewNode(4);
    root->right = getNewNode(6);

    root->left->left = getNewNode(2);
    root->left->right = getNewNode(2);
    root->right->left = getNewNode(3);
    root->right->right = getNewNode(3);
    
    return root;
}

/* Checks whether a tree satisfies the children sum 
 property or not. If tree satisfies children 
 sum property then it returns 1 otherwise 0 */
int isChildrenSumTree(struct node *root) {
    if(root == NULL)
        return 1;
    if(root->left == NULL && root->right == NULL)
        return 1;
    int leftData = (root->left == NULL) ? 0 : root->left->data;
    int rightData = (root->right == NULL) ? 0 : root->right->data;
    
    if(isChildrenSumTree(root->left) && isChildrenSumTree(root->right) && 
        (leftData + rightData == root->data))
        return 1;
    else 
        return 0;
}

int main() {
    struct node *root = generateBTree();    
    
    /* Check for Children sum property */
    if(isChildrenSumTree(root)){
        printf("Tree Satisfy Children Sum Property\n");
    } else {
        printf("Tree Don't Satisfy Children Sum Property");
    }
    /* Changing the value of a node such that 
    it won't satisfy children sum property */
    root->left->data = 100;
    if(isChildrenSumTree(root)){
        printf("Tree Satisfy Children Sum Property\n");
    } else {
        printf("Tree Don't Satisfy Children Sum Property");
    }
    getchar();
    return 0; 
}
Output
Tree Satisfy Children Sum Property
Tree Don't Satisfy Children Sum Property
Posted by
Labels: