# Root to leaf Path Sum

In this article, we are going to see how to check whether there exists a path from root leaf which has exactly the same sum given as input. This problem has been asked in coding round of Samsung, Microsoft, Adobe, Amazon etc
Submitted by Radib Kar, on December 07, 2018

Problem statement

Given a Binary Tree T and a sum S, write a program to check whether there is a root to leaf path in that tree with the input sum S.

Example: Fig: Binary Tree

In the above example, the root is 8 & the leaf nodes are 9,1,2,3. There are many root to leaf paths like:
8->5->9
8->5->7->1
8->5->7->12->2
And so on.

The sum for a root to leaf path is the sum of all intermediate nodes, the root & leaf node, i.e., sum of all the nodes on the path. Like for the first path in the above example the root to leaf path sum is 22 (8+5+9)

Our program must be to determine whether the given sum is same as anythe root to leaf path sum. There may be case that more than one root to leaf path has exactly same sum of S, but that’s not of any concern, Our function is a Boolean function to return only yes or not on basis of input.

Let for an example input:

S= 26 & T be the above binary tree in example

Our program should return "YES" as there is a root to leaf path exists which is 8->4->11->3

S=8 & T be the above binary tree in example

Our program should return "NO" as there is no root to leaf path exists which has sum 8

Algorithm

We need to construct a Boolean function hasRootToLeafSum () which will accept a sum value S & a binary tree T

We can implement the above function using recursion. The idea is to subtract current node value & continue to check for both subtrees recursively until we reach the base case. The base case can be of two type:

1. Root node for the subtrees are NULL & sum is 0 too. This is a valid terminating step. We return TRUE here.
2. The sum is 0 & we have reached a leaf node. This is of course the valid terminating step. We return TRUE here.

FunctionhasRootToLeafSum (sum value S, root of Binary tree T)

```1.  Set path to FALSE. Path represent the Boolean
variable which determines whether there is a root to leaf pathor not.
2.  Consider the base cases.
•   If (root==NULL&&S==0)  //case a
return true;
•   Subtract the root node value & check whether we have reached
the leaf node with remaining S, 0.
If (S==0 && root->left==NULL &&root->right==NULL)
return true;

3.	Recursively check for both right & left subtrees.
If(root->left) //for left subtree
path=path||hasRootToLeafSum (root->left, S);

If (root->right)//for right subtree
path=path||hasRootToLeafSum (root->right, S);

4.	Return path ( FALSE or TRUE)

If the function return FALSE then no path is found else there is a path.
```

## C++ implementation of Root to leaf Path Sum

```#include<bits/stdc++.h>
using namespace std;

class tree{ //tree node
public:
int data;
tree *left;
tree *right;
};

bool hasRootToLeafSum(tree *root, int s){
bool path=false; //declare boolean variable path
//base condition checking
if(root==NULL && s==0)
return true;

s-=root->data; //subtract current root value

//checking whether leaf node reached and remaining sum =0
if(s==0 && root->left==NULL && root->right==NULL)
return true;
//recursively done for both subtrees
if(root->left){//for left subtree
path=path||hasRootToLeafSum(root->left, s);
}
if(root->right){//for right subtree
path=path||hasRootToLeafSum(root->right, s);
}
return path;
}

tree* newnode(int data){  //creating new nodes
tree* node = (tree*)malloc(sizeof(tree));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}

int main() {
//**same tree is builted as shown in example**
cout<<"tree in the example is build here"<<endl;
//building the tree like as in the example
tree *root=newnode(8);
root->left= newnode(5);
root->right= newnode(4);
root->right->right=newnode(11);
root->right->right->left=newnode(3);
root->left->left=newnode(9);
root->left->right=newnode(7);
root->left->right->left=newnode(1);
root->left->right->right=newnode(12);
root->left->right->right->left=newnode(2);

int s;

cout<<"enter input sum S......"<<endl;
cin>>s;

if(hasRootToLeafSum(root,s))//if there exists such a path
cout<<"A root to leaf path with this sum  exists"<<endl;
else
cout<<"No such a path exists"<<endl;

return 0;
}
```

Output

```First run:
tree in the example is build here
enter input sum S......
26
A root to leaf path with this sum  exists

Second run:
tree in the example is build here
enter input sum S......
8
No such a path exists
```