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

Thanks for reading!

Tanishq Chaudhary

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