A binary tree and an integer K are given. Our goal is to return whether there is a root-to-leaf path in the tree such that it’s sum is equal to the target-K. The sum of a path is the sum of all nodes that lie on it.

2 / \ 1 4 / \ 1 4 K = 7

Path Present

2 / \ 1 4 / \ 1 3 K = 6

No such path

Table of Contents

## Approach

The approach is pretty simple. We can check that if at a certain point, the value of a node is what we need, and it is a leaf as well. Then, we can conclude that a path exists from root to this point having target sum. So, it is intuitive that as we recursively jump to any child, we must pass on the remaining sum to complete the target.

This idea works in a single pass of the tree.

## Algorithm

- Create a recursive helper function
- Helper function has the current node details and the remaining sum
- If the current root is
**NULL,**- return
**false,**as this node can’t contribute anything.

- return
- If the current root is
**NOT NULL**- If the sum required is equal to node value and the node is a leaf
- return true

- else
- check if any left or child subtree satisfies the need with required sum: current_sum – node_value

- If the sum required is equal to node value and the node is a leaf
- Print the output

## Implementation

### C++ Program to find Root to Leaf path with target sum

#include <bits/stdc++.h> using namespace std; struct treeNode { int value; treeNode *left , *right; treeNode(int x) { value = x; left = NULL; right = NULL; } }; bool pathSumEqualToTarget(treeNode* root , int target) { if(!root) return false; if(target == root->value && !root->left && !root->right) return true; return pathSumEqualToTarget(root->left , target - root->value) || pathSumEqualToTarget(root->right , target - root->value); } int main() { treeNode* root = new treeNode(2); root->left = new treeNode(1); root->right = new treeNode(4); root->right->left = new treeNode(1); root->right->right = new treeNode(4); int K = 7; if(pathSumEqualToTarget(root , K)) cout << "Path Present" << '\n'; else cout << "No such path" << '\n'; }

### Java Program to find Root to Leaf path with target sum

class treeNode { int value; treeNode left , right; public treeNode(int x) { value = x; left = right = null; } } class path_sum { public static boolean pathSumEqualToTarget(treeNode root , int target) { if(root == null) return false; if(root.value == target && root.left == null && root.right == null) return true; return pathSumEqualToTarget(root.left , target - root.value) || pathSumEqualToTarget(root.right , target - root.value); } public static void main(String args[]) { treeNode root = new treeNode(2); root.left = new treeNode(1); root.right = new treeNode(4); root.right.left = new treeNode(1); root.right.right = new treeNode(4); int K = 7; if(pathSumEqualToTarget(root , K)) System.out.println("Path Present"); else System.out.println("No such path"); } }

## Complexity Analysis

### Time Complexity to find Root to Leaf path with target sum

**O(N)**, as the program works in a single pass of the binary tree in the worst case.

### Space Complexity to find Root to Leaf path with target sum

**O(N). **Recursion uses auxiliary stack space.