# LeetCode - Path Sum

## Problem statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equal targetSum.

A leaf is a node with no children.

Problem statement taken from: https://leetcode.com/problems/path-sum

Example 1:

``````Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
``````

Example 2:

``````Input: root = [1, 2, 3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with a sum = 5.
``````

Example 3:

``````Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.
``````

Constraints:

``````- The number of nodes in the tree is in the range [0, 5000].
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
``````

### Explanation

#### Recursion

For solving most of the tree-related problems, the best ways are to go with the recursion approach or using queues/stacks.

It is one of the easy problems which we will solve using recursion. We follow the given steps to solve the problem:

• Recursively move to the left and right subtree. At each recursive call, decrease the sum by the value of the current node.

• At any recursive call, if the current node value is equal to the remaining sum return true. This means a path exists with the given target.

Let's check the algorithm first.

``````- if root == null
- return false

- if root->val == targetSum && root->left == null && root->right == null
- return true

- remainingTarget = targetSum - root->val

- return hasPathSum(root->left, remainingTarget) || hasPathSum(root->right, remainingTarget)
``````

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == NULL) {
return false;
}

if(root->val == targetSum && root->left == NULL && root->right == NULL) {
return true;
}

int remainingTarget = targetSum - root->val;

return hasPathSum(root->left, remainingTarget) || hasPathSum(root->right, remainingTarget);
}
};``````

#### Golang solution

``````func hasPathSum(root *TreeNode, targetSum int) bool {
if root == nil {
return false
}

if root.Val == targetSum && root.Left == nil && root.Right == nil {
return true
}

remainingTargetSum := targetSum - root.Val

return hasPathSum(root.Left, remainingTargetSum) || hasPathSum(root.Right, remainingTargetSum)
}``````

#### Javascript solution

``````var hasPathSum = function(root, targetSum) {
if(root == null) {
return false;
}

if(root.val == targetSum && root.left == null && root.right == null) {
return true;
}

let remainingTarget = targetSum - root.val;

return hasPathSum(root.left, remainingTarget) || hasPathSum(root.right, remainingTarget);
};``````

#### Dry Run

Let's dry-run our algorithm for Example 1.

``````Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]
targetSum = 22

Step 1: if root == null
the root is at 5
false

Step 2: if root->val == targetSum && root->left == NULL && root->right == NULL
5 == 22
false

Step 3: remainingTarget = targetSum - root->val
= 22 - 5
= 17

Step 4: return hasPathSum(root->left, remainingTarget) ||
hasPathSum(root->right, remainingTarget)

root->left = 4
root->right = 8
remainingTarget = 17

Step 5: if root == null
the root is at 4
false

Step 6: if root->val == targetSum && root->left == NULL && root->right == NULL
4 == 17
false

Step 7: remainingTarget = targetSum - root->val
= 17 - 4
= 13

Step 8: return hasPathSum(root->left, remainingTarget) ||
hasPathSum(root->right, remainingTarget)

root->left = 11
root->right = nil
remainingTarget = 13

Step 9: if root == null
the root is at 11
false

Step 10: if root->val == targetSum && root->left == NULL && root->right == NULL
11 == 13
false

Step 11: remainingTarget = targetSum - root->val
= 13 - 11
= 2

Step 12: return hasPathSum(root->left, remainingTarget) ||
hasPathSum(root->right, remainingTarget)

root->left = 7
root->right = 2
remainingTarget = 2

Step 13: if root == null
the root is at 7
false

Step 14: if root->val == targetSum && root->left == NULL && root->right == NULL
7 == 2
false

Step 15: remainingTarget = targetSum - root->val
= 2 - 7
= -5

Step 16: return hasPathSum(root->left, remainingTarget) ||
hasPathSum(root->right, remainingTarget)

root->left = null
root->right = null
remainingTarget = -5

Step 17: if root == null
the root is null
true

We backtrack to Step 16

Step 18: if root == null
the root is null
true

We backtrack to Step 12

Step 19: if root == null
the root is at 2
false

Step 20: if root->val == targetSum && root->left == NULL && root->right == NULL
2 == 2
true

We return true here and backtrack for the rest of the tree.
In the end, we have OR condition and have found the path once
we return the answer as true.
``````