# Path Sum III | Solution Explained

LeetCode 437. Path Sum III. I explain the brute-force solution and the optimized solutions in detail for reducing O(N^2) to O(N) time. Problem Link.

## 1. Path Sum III: Brute-force

### 1.0. Core Logic

Focusing on the line, “The path does not need to start or end at the root or a leaf, …“, we can conclude that we can start from any point.

In other words, we can restart our counting of the path sum from anywhere we like. We can either:

• start the sum counting from 0 – restarting
• continue the sum from what the parent gave us

### 1.1. Formalized Logic

Let’s formalize this. Since we want to search for a path in a tree, we are going to use depth first search (DFS). It takes in the input as `dfs(node, curr, reset)` where:

• `node`: the current node in consideration
• `curr`: the current path sum
• `reset`: whether a request for resetting the curr was sent or not. NOTE we can’t directly check for `curr == 0` to know if the sum has resetted – there can be cases like `x+y = 0` where `x = 2, y = -2`. In this case, no reset request is sent.

We generate 4 dfs-es from this point:

• `dfs(node.left, curr, 0)`
• `dfs(node.right, curr, 0)`
• `dfs(node.left, 0, 1)`
• `dfs(node.right, curr, 0)`

Finally, we have to consider cases of repetition. Consider:

In this case, say we start from x. We go to y with score x. From y we go to z with curr as x+y (due to cumulative effect).

At the point z, one of the cases I’ll consider is the case of resetting. This is fine and perfectly allowed.

Let’s take another case. Instead of starting from x, let’s say this time y sends a reset request.

Now the curr becomes 0. At the point x, we receive curr = y. What if … we again decide to reset at point z?

This essentially means we are considering the same node again and again. To prevent that, we have additional logic for handling resetted nodes.

### 1.2. Code

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:

def dfs(node, curr, reset):
if not node: return 0
if node in resetted and reset: return 0
if curr == 0 and reset: resetted.add(node)

count = 0
curr += node.val
if curr == targetSum: count += 1

count += dfs(node.left, curr, 0)
count += dfs(node.right, curr, 0)
count += dfs(node.left, 0, 1)
count += dfs(node.right, 0, 1)

return count

resetted = set()
return dfs(root, 0, 1)
```

### 1.3. Complexity

• Time: `O(N^2)` since for each node, we have to explore 4 more cases for the rest of the nodes. Basically, `O(N*4N)`.
• Space: `O(N)`. `O(N)` for storing resetted and `O(N)` for the height of the recursion call stack height.

## 2. Path Sum III: Optimization

The idea of cumulative sums is interesting. Perhaps we can exploit that.

Consider a 1D case, of an array. We just take the left branch of the tree: `[10, 5, 3, 3]`

Let’s say we have the goal of querying the array for sum, as `sum(i:j)`. This operation can take `O(N)` worst case time. But, how can we reduce it to `O(1)`?

We can find out the cumulative sums.

In this way, we can query in `O(1)` time:

Coming back to the Path Sum III question, we can replace the logic for the resetting thing with cumulative sum logic. We are anyways computing the cumulative sum as `curr += node.val`. Now, we have one big issue.

In arrays it is rather easy to calculate the difference because we have access to the elements in O(1) time in the `cumu` array.

For this case, we have to create a data structure that can store all of the values it has accessed. We can create a `count = defaultdict(int)` in Python3.

`count` is a dictionary as `key = node.val : value = count/frequency`.

Before calling `dfs(node.left/right, curr)`, we are going to set `count[curr+targetSum] += 1`, since we want to bait a future dfs call with `curr(future) == curr(now) + targetSum`. If that happens, we happily do `ans += count[curr]` saying that the frequency stored before is valid since we have reached an end point where the diff of `curr(future)` and `curr(now)` is the same as `targetSum`. Perhaps the visualization & code makes things clear :sweat_smile:

### 2.1. Code

```class Solution:
def pathSum(self, root, targetSum):

def dfs(node, curr):
if not node: return

nonlocal ans, count

curr += node.val
ans += count[curr]
# if you need help understanding the solution
# print(f"node: {node.val}:: curr: {curr}, count: {count[curr]}\ncount={count}\n\n")
count[curr+targetSum] += 1
dfs(node.left, curr)
dfs(node.right, curr)
count[curr+targetSum] -= 1

ans = 0
count = defaultdict(int)
count[targetSum] = 1
dfs(root, 0)
return ans
```

### 2.2. Complexity Analysis

• Time: `O(N)` since we go over all the nodes only once.
• Space: `O(N)` since we store the `count` dictionary & `O(N)` more for the height of the recursion call stack.

##### Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Seats | InterviewBit | Solution Explained

June 13, 2022