Path Sum III

Problem

Qn - Path Sum III

Approach

My first idea was to do dfs but with some minor adjustments. While dfsing, we keep track of an array of all the possible sums that we have seen before. When going down one level, for every element in the array, we add the current value and check if it hits the target sum, and also append the current value into the array.

The second approach took me a while to understand it.

I think this visualisation will help a bunch. Basically, we can keep a running sum from the root all the way down, and the way we know that we have passed a path that sums up to the target sum, we can just use currSum - targetSum, if it exists in the dictionary of all the current sums we have been tracking that means we have found a path.

Some things that you might forget, is that we need to do some backtracking and remove the currSum from the dictionary when we have completed exploring the left and right child, as that node will not be part of the path anymore. We also need to ensure that we need to initialise the dictionary with {0: 1}, we always have a sum of 0.

https://www.youtube.com/watch?v=6jYxwdwjwKg

Complexity

• Time: O(n)
• Space: O(n)

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:
        lookup = defaultdict(int)
        lookup[0] += 1
 
        def dfs(node, curr_sum):
            if not node: return 0
 
            curr_sum += node.val
            count = lookup[curr_sum - targetSum]
            lookup[curr_sum] += 1
            count += dfs(node.left, curr_sum)
            count += dfs(node.right, curr_sum)
            lookup[curr_sum] -= 1
 
            return count
        
        return dfs(root, 0)

The first approach

# 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:
        res = 0
 
        def dfs(node):
            nonlocal res
            if not node: return []
 
            val = node.val
            if val == targetSum: res += 1
            inter = dfs(node.left) + dfs(node.right)
            for i,v in enumerate(inter):
                if v + val == targetSum: res += 1
                inter[i] += val
            inter.append(val)
            return inter
 
        dfs(root)
 
        return res