Check for Children-Sum property in Binary Tree

As an Input We are Given a tree and we have to check for children sum property. Whether that property if followed in an entire tree or not.

Note:- Deviation of even single Node from above property will result in a negative answer.

Children-Sum Property:-This property says that for each node sum of its left and right children should be equal to node value.

Also, following assumptions are to be kept in mind while recursively traversing tree

  1. A leaf node satisfies children sum property because leaf nodes don’t have any child nodes.
  2. An Empty tree satisfies Children sum property.

Algorithm:-

Step1:- Traverse the tree.
Step 2:- For every node in tree check whether the value in root node equals the sum of it lchild and rchild.

If yes continue from Step 1 Untill root==NULL

If No return false

The time complexity for above program is O(n). Since each node is covered once.

Readers are requested to submit their codes in different languages and optimised ones if any in the comment section below.

Code:-

[code language=”cpp”]

#include<bits/stdc++.h>

struct Treenode// definition of structure of tree node which has lchild child and rchild child
{
int val;
Treenode* lchild;
Treenode* rchild;
};

struct Treenode* newNode(int key)// function for new node creation
{ /* dynamically allocate memory for a new node */
struct Treenode* newnode = (struct Treenode*)malloc(sizeof(struct Treenode));
newnode->val = key;
newnode->lchild = NULL;
newnode->rchild = NULL;

return(newnode);
}
/*
This function returns a binary tree which
satisfy children sum property */
int TreefollowingChildSumProperty(Treenode* head)
{
/* two temporrary values to store the values from left tree
and right tree*/
int lchild_val = 0, rchild_val = 0;

if(head == NULL ||
(head->lchild == NULL && head->rchild == NULL))
return 1;
else
{

if(head->lchild != NULL)
lchild_val = head->lchild->val;

if(head->rchild != NULL)
rchild_val = head->rchild->val;

/* now check whether the value of node head is equal to value of lchild and rchild
and does same applies for further parts or not*/
if((head->val == lchild_val + rchild_val)&&
TreefollowingChildSumProperty(node->lchild) &&
TreefollowingChildSumProperty(node->rchild))
return 1;
else
return 0;
}
}

int main()
{
Treenode *root1 = newNode(232);
Treenode *root2 = newNode(232);// these part is concerned with creation of tree
// user can edit this as per wish
root1->lchild = newNode(231);
root1->rchild = newNode(231);
root1->lchild->lchild = newNode(431);
root1->lchild->rchild = newNode(531);

root2->lchild = newNode(231);
root2->rchild = newNode(331);
root2->lchild->lchild = newNode(431);
root2->lchild->rchild = newNode(513);

if(TreefollowingChildSumProperty(root))
cout<<"Given Tree Follows children Sum Property\n";
else
cout<<"Tree does not follows Children Sum property\n";

getchar();
return 0;
}

[/code]