Root to leaf path with sum equal to given sum

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.

Binary Tree

In above tree, root to leaf paths exists for following sum.

7=> 1->2->4

9=> 1->3->5


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
		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;

3 Thoughts on “Root to leaf path with sum equal to given sum

  1. int sumpresent(tree *root, int sum)
    int newsum;
    if (NULL == root)
    return (0 == sum);
    newsum = sum – root->value;
    if (0 == newsum)
    return 1;
    if (newsum > 0)
    return sumpresent(root->left,newsum) || sumpresent(root->right,newsum);
    return 0;


  2. int currsum=0;
    bool returnLeafPath(struct node *root,int sum)
    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?

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