Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

437. Path Sum III - Leetcode Solution

Code Implementation

# 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: TreeNode, targetSum: int) -> int:
        from collections import defaultdict

        def dfs(node, curr_sum):
            if not node:
                return 0
            curr_sum += node.val
            res = prefix_sums[curr_sum - targetSum]
            prefix_sums[curr_sum] += 1
            res += dfs(node.left, curr_sum)
            res += dfs(node.right, curr_sum)
            prefix_sums[curr_sum] -= 1
            return res

        prefix_sums = defaultdict(int)
        prefix_sums[0] = 1
        return dfs(root, 0)
      
// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        unordered_map<int, int> prefixSums;
        prefixSums[0] = 1;
        return dfs(root, 0, sum, prefixSums);
    }
    
    int dfs(TreeNode* node, int currSum, int target, unordered_map<int, int>& prefixSums) {
        if (!node) return 0;
        currSum += node->val;
        int res = prefixSums[currSum - target];
        prefixSums[currSum]++;
        res += dfs(node->left, currSum, target, prefixSums);
        res += dfs(node->right, currSum, target, prefixSums);
        prefixSums[currSum]--;
        return res;
    }
};
      
// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> prefixSums = new HashMap<>();
        prefixSums.put(0, 1);
        return dfs(root, 0, sum, prefixSums);
    }
    
    private int dfs(TreeNode node, int currSum, int target, Map<Integer, Integer> prefixSums) {
        if (node == null) return 0;
        currSum += node.val;
        int res = prefixSums.getOrDefault(currSum - target, 0);
        prefixSums.put(currSum, prefixSums.getOrDefault(currSum, 0) + 1);
        res += dfs(node.left, currSum, target, prefixSums);
        res += dfs(node.right, currSum, target, prefixSums);
        prefixSums.put(currSum, prefixSums.get(currSum) - 1);
        return res;
    }
}
      
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var pathSum = function(root, targetSum) {
    const prefixSums = new Map();
    prefixSums.set(0, 1);

    function dfs(node, currSum) {
        if (!node) return 0;
        currSum += node.val;
        let res = prefixSums.get(currSum - targetSum) || 0;
        prefixSums.set(currSum, (prefixSums.get(currSum) || 0) + 1);
        res += dfs(node.left, currSum);
        res += dfs(node.right, currSum);
        prefixSums.set(currSum, prefixSums.get(currSum) - 1);
        return res;
    }
    return dfs(root, 0);
};

Problem Description

The Path Sum III problem asks you to find the total number of paths in a binary tree where the sum of the node values along the path equals a given targetSum. These paths do not need to start at the root or end at a leaf, but they must go downwards (from parent to child nodes). Each node may only be used once per path, and the tree may contain negative values. The goal is to count all such valid paths in the tree.

Thought Process

To solve this problem, one might first think of brute-forcing: for every node, try every possible downward path and check if the sum equals targetSum. However, this quickly becomes inefficient as the number of nodes grows, since you'd be recalculating many of the same sums repeatedly. The key insight is to recognize that the problem is similar to the "subarray sum equals k" problem, but on a tree. Instead of recalculating sums for every path, we can keep track of the cumulative sum from the root to the current node and use a hash map to store how many times each cumulative sum has occurred. This allows us to efficiently determine how many previous paths could be extended to form a path that sums to targetSum.

Solution Approach

The optimized solution uses prefix sums and a hash map to keep track of cumulative sums as we traverse the tree. Here’s how the algorithm works:
  1. We perform a depth-first traversal of the tree, keeping track of the current cumulative sum from the root to the current node.
  2. We use a hash map (prefixSums) to record how many times a particular cumulative sum has occurred so far.
  3. At each node, we check if there is a prefix sum such that currentSum - targetSum exists in the map. If it does, it means there is a path ending at the current node whose sum is targetSum.
  4. We increment the count of the current cumulative sum in the map before traversing the children, and decrement it after visiting both children (backtracking step), to ensure the prefix sum count is correct for different paths.
  5. The base case is when the node is null, in which case we return 0.
This approach ensures that each path is considered exactly once and avoids redundant calculations, making it efficient even for large trees.

Example Walkthrough

Consider the following tree and targetSum = 8:

       10
      /  \
     5   -3
    / \    \
   3   2    11
  / \   \
 3  -2   1
  • Start at 10: cumulative sum is 10. No matching prefix sum yet.
  • Move to 5: cumulative sum is 15. Check if 15-8=7 exists in prefix map (it doesn't).
  • Move to 3: cumulative sum is 18. Check if 18-8=10 exists (it does, so one path).
  • Move to 3: cumulative sum is 21. Check if 21-8=13 exists (it doesn't).
  • Backtrack and check -2: cumulative sum is 16. 16-8=8 doesn't exist.
  • Backtrack to 2: cumulative sum is 17. 17-8=9 doesn't exist.
  • Move to 1: cumulative sum is 18. 18-8=10 exists (so another path).
  • Backtrack to -3: cumulative sum is 7. 7-8=-1 doesn't exist.
  • Move to 11: cumulative sum is 18. 18-8=10 exists (so another path).

In total, there are 3 valid paths that sum to 8: [5,3], [5,2,1], and [-3,11].

Time and Space Complexity

  • Brute-force approach: For each node, start a new path and try all possible downward paths. This leads to O(N^2) time complexity in the worst case (a skewed tree), since every node could be the start of a path, and for each, you may traverse all descendants. Space complexity is O(H) for recursion stack (H = tree height).
  • Optimized approach (prefix sum + hash map): Each node is visited once, and hash map operations are O(1) on average. So, time complexity is O(N), where N is the number of nodes. Space complexity is O(N) due to the hash map and recursion stack in the worst case (unbalanced tree).

Summary

The Path Sum III problem is efficiently solved by using prefix sums and a hash map while traversing the tree with depth-first search. This approach avoids redundant work and leverages the cumulative sum concept to find all valid paths in O(N) time. The key insight is to recognize the relationship between current and previous sums to quickly identify valid paths, making the solution both elegant and efficient.