# 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.
```