Massive Algorithms: Check for Children Sum Property in a Binary Tree.

Check for Children Sum Property in a Binary Tree. | GeeksforGeeks
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. Below tree is an example

int isSumProperty(struct node* node)

{

  /* left_data is left child data and right_data is for right child data*/

  int left_data = 0,  right_data = 0;

  /* If node is NULL or it's a leaf node then

     return true */

  if(node == NULL ||

     (node->left == NULL && node->right == NULL))

    return 1;

  else

{

    /* If left child is not present then 0 is used

       as data of left child */

    if(node->left != NULL)

      left_data = node->left->data;

    /* If right child is not present then 0 is used

      as data of right child */

    if(node->right != NULL)

      right_data = node->right->data;

    /* if the node and both of its children satisfy the

       property return 1 else 0*/

    if((node->data == left_data + right_data)&&

        isSumProperty(node->left) &&

        isSumProperty(node->right))

      return 1;

    else

      return 0;

}

}

Method 2:Twice Sum Method

int isLeaf(struct node *node)

{

if(node == NULL)

return 0;

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

return 1;

return 0;

}

int isSumTree(struct node* node)

{

int ls;

int rs;

if(node == NULL || isLeaf(node))

return 1;

if( isSumTree(node->left) && isSumTree(node->right))

{

if(node->left == NULL)

ls = 0;

else if(isLeaf(node->left))

ls = node->left->data;

else

ls = 2*(node->left->data);

if(node->right == NULL)

rs = 0;

else if(isLeaf(node->right))

rs = node->right->data;

else

rs = 2*(node->right->data);

return(node->data == ls + rs);

}

return 0;

}

Labels