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.
0. Setup


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 considerationcurr
: the current path sumreset
: whether a request for resetting the curr was sent or not. NOTE we can’t directly check forcurr == 0
to know if the sum has resetted – there can be cases likex+y = 0
wherex = 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 andO(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 thecount
dictionary &O(N)
more for the height of the recursion call stack.
Thanks for reading!
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