Given a binary tree and a number,Write a function to find out whether there is a path from root to leaf with sum equal to given Number.
In above tree, root to leaf paths exists for following sum.
7=> 1->2->4
9=> 1->3->5
10=>1->3->6
Implementation :
struct node{
struct node *left;
struct node *right;
int value;
};
bool pathWithGivenSum(struct node* root,int sum)
{
// return true if we run out of tree and sum==0
if(root==NULL)
return (sum==0);
if(root->left==NULL && root->right==NULL)
return (sum==root->value);
int currentSum = sum - root->value;
if(root->left && pathWithGivenSum(root->left,currentSum))
return true;
if(root->right && pathWithGivenSum(root->right,currentSum))
return true;
return false;
}
int sumpresent(tree *root, int sum)
{
int newsum;
if (NULL == root)
return (0 == sum);
newsum = sum – root->value;
if (0 == newsum)
return 1;
else
if (newsum > 0)
return sumpresent(root->left,newsum) || sumpresent(root->right,newsum);
else
return 0;
}
this will not work. The lines
if (0 == newsum)
return 1;
do not ensure that we are at a leaf node
int currsum=0;
bool returnLeafPath(struct node *root,int sum)
{
currsum+=root->data;
if(currsum>sum)
{
currsum-=root->data;
return false;
}
if(currsum==sum && root->left == NULL && root->right == NULL)
{
return true;
}
return (returnLeafPath(root->left,sum) || returnLeafPath(root->right,sum));
}
Would this work?