  # LeetCode - Path Sum III

## Problem statement

Given the `root` of a binary tree and an integer `targetSum`, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

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

Example 1: ``````Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.
``````

Example 2:

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

Constraints:

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

### Explanation

#### Recursion

The problem is similar to our previous blog posts Path Sum and Path Sum II.

We need to change the algorithm a bit to count the different paths in the tree. We will use the DFS algorithm to count the paths. Let's check the algorithm.

``````// pathSum method
- if root == null
- return 0

- return dfs(root, 0, targetSum) +
pathSum(root->left, targetSum) +
pathSum(root->right, targetSum)

// dfs method
- if root == null
- return 0

- set currentSum = previousSum + root->val
count = 0

- if currentSum == targetSum
- count = 1

- return count +
dfs(root->left, currentSum, targetSum) +
dfs(root->right, currentSum, targetSum)
``````

The time-complexity can be reduced to O(nlog(n)) by reversing the linked list.

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

#### C++ solution

``````class Solution {
public:
int dfs(TreeNode* root, long long previousSum, long long targetSum) {
if(root == NULL) {
return 0;
}

int currentSum = previousSum + root->val;
int count = 0;

if(currentSum == targetSum) {
count = 1;
}

return count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum);
}

int pathSum(TreeNode* root, int targetSum) {
if(root == NULL) {
return 0;
}

return dfs(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
}
};``````

#### Golang solution

``````func dfs(root *TreeNode, previousSum, targetSum int) int {
if root == nil {
return 0
}

currentSum := previousSum + root.Val

count := 0

if currentSum == targetSum {
count = 1
}

return count + dfs(root.Left, currentSum, targetSum) + dfs(root.Right, currentSum, targetSum)
}

func pathSum(root *TreeNode, targetSum int) int {
if root == nil {
return 0
}

return dfs(root, 0, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}``````

#### Javascript solution

``````var dfs = function(root, previousSum, targetSum) {
if(root == null) {
return 0;
}

let currentSum = previousSum + root.val;
let count = 0;

if(currentSum == targetSum) {
count = 1;
}

return count + dfs(root.left, currentSum, targetSum) + dfs(root.right, currentSum, targetSum);
};

var pathSum = function(root, targetSum) {
if(root == null) {
return 0;
}

return dfs(root, 0, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

``````Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]
targetSum = 8

// pathSum method
Step 1: if root == NULL
root -> 10
false

Step 2: dfs(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum)
dfs(->10, 0, 8) + pathSum(->5, 8) + pathSum(-3, 8)

// dfs method
Step 3: if root == NULL
root -> 10
false

currentSum = previousSum + root->val
= 0 + 10
= 10

count = 0

currentSum == targetSum
10 == 8
false

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->5, 10, 8) + dfs(->(-3), 10, 8)

// dfs(->5, 10, 8)
Step 4: if root == NULL
root -> 5
false

currentSum = previousSum + root->val
= 10 + 5
= 15

count = 0

currentSum == targetSum
15 == 8
false

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->3, 15, 8) + dfs(2, 15, 8)

// dfs(->3, 15, 8)
Step 5: if root == NULL
root -> 3
false

currentSum = previousSum + root->val
= 15 + 3
= 18

count = 0

currentSum == targetSum
18 == 8
false

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->3, 18, 8) + dfs(->(-2), 18, 8)

// dfs(->3, 18, 8)
Step 6: if root == NULL
root -> 3
false

currentSum = previousSum + root->val
= 18 + 3
= 21

count = 0

currentSum == targetSum
21 == 8
false

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 21, 8) + dfs(->nil, 21, 8)

Both dfs(->nil, 21, 8), dfs(->nil, 21, 8) node is nil so we return 0 and backtrack to Step 5
0 + dfs(->3, 18, 8) + dfs(->(-2), 18, 8) where we solve for
dfs(->(-2), 18, 8)

// dfs(->(-2), 18, 8)
Step 7: if root == NULL
root -> -2
false

currentSum = previousSum + root->val
= 21 + -2
= 19

count = 0

currentSum == targetSum
19 == 8
false

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 19, 8) + dfs(->nil, 19, 8)

Both dfs(->nil, 19, 8), dfs(->nil, 19, 8) node is nil so we return 0 and backtrack to Step 4
0 + dfs(->3, 15, 8) + dfs(2, 15, 8) where we solve for
dfs(2, 15, 8)

// dfs(2, 15, 8)
Step 8: if root == NULL
root -> 2
false

currentSum = previousSum + root->val
= 15 + 2
= 17

count = 0

currentSum == targetSum
17 == 8
false

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 17, 8) + dfs(1, 17, 8)

dfs(->nil, 17, 8) returns 0 as node is nil, so we evaluate for
dfs(1, 17, 8)

// dfs(1, 17, 8)
Step 9: if root == NULL
root -> 1
false

currentSum = previousSum + root->val
= 17 + 1
= 18

count = 0

currentSum == targetSum
18 == 8
false

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 18, 8) + dfs(->nil, 18, 8)

Both dfs(->nil, 19, 8), dfs(->nil, 19, 8) node is nil so we return 0 and backtrack to Step 3
0 + dfs(->5, 10, 8) + dfs(->(-3), 10, 8) where we solve for
dfs(->(-3), 10, 8)

// dfs(->(-3), 10, 8)
Step 10: if root == NULL
root -> -3
false

currentSum = previousSum + root->val
= 10 + -3
= 7

count = 0

currentSum == targetSum
7 == 8
false

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 7, 8) + dfs(->11, 7, 8)

dfs(->nil, 7, 8) returns 0 as node is nil, so we evaluate for
dfs(->11, 7, 8)

// dfs(->11, 7, 8)
Step 11: if root == NULL
root -> 11
false

currentSum = previousSum + root->val
= 7 + 11
= 18

count = 0

currentSum == targetSum
18 == 8
false

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 18, 8) + dfs(->nil, 18, 8)

Both dfs(->nil, 18, 8), dfs(->nil, 18, 8) node is nil so we return 0 and backtrack to Step 2
dfs(->10, 0, 8) + pathSum(->5, 8) + pathSum(-3, 8)
where we have dfs(->10, 0, 8) as 0
and we evaluate for pathSum(->5, 8)

// pathSum(->5, 8)
Step 12: if root == NULL
root -> 5
false

dfs(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum)
dfs(->5, 0, 8) + pathSum(->3, 8) + pathSum(->2, 8)

// dfs(->5, 0, 8)
Step 13: if root == NULL
root -> 5
false

currentSum = previousSum + root->val
= 0 + 5
= 5

count = 0

currentSum == targetSum
5 == 8
false

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->3, 5, 8) + dfs(->2, 5, 8)

// dfs(->3, 5, 8)
Step 14: if root == NULL
root -> 3
false

currentSum = previousSum + root->val
= 5 + 3
= 8

count = 0

currentSum == targetSum
8 == 8
true
count = 1

count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
1 + dfs(->3, 8, 8) + dfs(->(-2), 8, 8)

We similarly iterate over the rest of the tree and return the count.
``````