# Root to Leaf Path having sum X in the given Tree

In this article, we are going to see **how to find whether there is any root to leaf path having sum X in the given tree?**

Submitted by Radib Kar, on September 10, 2020

Here, we are going to see how we can find whether the given tree has any root to leaf path having sum *X*?

In the below example,

In the above given tree, if sum *X* is 14, then we find a root to leaf path which is marked in the above tree ( 5->3->2->4)

But, if sum *X* is 13, then we don't find any root to leaf path having the sum.

**Solution:**

We can solve this recursively like the below algorithm:

We keep calculating sum from the root and if reaching any node the cumulative sum becomes *X*, then we find a path having sum *X*.

Initially, *cur_sum* is 0 which stores cumulative sum for paths.

Function hasPathSumRecur(node, sum X , cur_sum): If root is NULL return FALSE; Add current node value to cur_sum If current node is a leaf node & && cur_sum equals to X return TRUE as we find a path; Otherwise recur for both the subtrees and if we find any one satisfying then return TRUE else FALSE

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; // tree node is defined class TreeNode { public: int val; TreeNode* left; TreeNode* right; TreeNode(int data) { val = data; left = NULL; right = NULL; } }; bool hasPathSumRecur(TreeNode* root, int sum, int cur_sum) { if (!root) return false; cur_sum += root->val; if (!root->left && !root->right && cur_sum == sum) return true; return hasPathSumRecur(root->left, sum, cur_sum) || hasPathSumRecur(root->right, sum, cur_sum); } bool hasPathSum(TreeNode* root, int sum) { int cur_sum = 0; return hasPathSumRecur(root, sum, cur_sum); } int main() { //building the tree like the example TreeNode* root = new TreeNode(5); root->left = new TreeNode(3); root->right = new TreeNode(4); root->left->left = new TreeNode(1); root->left->right = new TreeNode(2); root->right->right = new TreeNode(3); root->left->right->left = new TreeNode(4); int sum = 14; if (hasPathSum(root, sum)) cout << "There is a root to leaf path having sum: " << sum << endl; else cout << "There is no root to leaf path having sum: " << sum << endl; sum = 13; if (hasPathSum(root, sum)) cout << "There is a root to leaf path having sum: " << sum << endl; else cout << "There is no root to leaf path having sum " << sum << endl; return 0; }

**Output:**

There is a root to leaf path having sum: 14 There is no root to leaf path having sum 13

**Dry run:**

Initially, *cur_sum* is 0, *X*=14 and given tree is the same as the example.

Below are the steps for a dry run:

Now it recurs for the right child of 1 which is again NULL and thus controls returns back to node 3. And now there we recur for the right subtree of 3

So, we find a path here and it returns true.

You can do the dry run taking *X*=13 and you will find that no path has the sum 13.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.