Monday, July 24, 2006

Tree sum

/***
Given a tree and a sum, write an algorithm to return TRUE if there is a path from the root node down to a leaf such that adding all values of the nodes along the path equals the given sum.
***/

BOOLEAN rootToLeafSumEqualsInput(NODE *root,int sum)
{
if(root.left == NULL && root.right == NULL)
{
if(root.value == sum)
{
printf root.value;
return TRUE;
}
else
return FALSE;
}
if(root.left != NULL)
{
if(rootToLeafSumEqualsInput(root.left,(sum - root.value)) == TRUE)
{
printf root.value;
return TRUE;
}
}
if(root.right != NULL)
{
if(rootToLeafSumEqualsInput(root.left,(sum - root.value)) == TRUE)
{
printf root.value;
return TRUE;
}
}
}

4 comments:

Achuth said...

after if(root.right != NULL )

recursion func should be called on root.right ! ..

Please correct If I am wrong

Achuth said...

can you please provide an efficient algo for to find a pair of integers in an array whose sum is equal to 25 ( or SUM in general )

Thanks
Achuth R

Ghotter said...

its already there..

Ghotter said...

for the question you asked, it can be done in the following manner.

Say the given Array is Arr
sort Arr
for each elem in Arr find if
Sum - elem is there in the array.
(for finding the sum use binary search)