Check for Children Sum Property in a Binary Tree

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)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation