437. Path Sum III

Problem Description

The problem involves finding the number of paths in a binary tree that sum up to a given target value. The key aspects to remember are:

A path is a sequence of nodes where each subsequent node is a direct child of the previous node.
Unlike some other path problems, the paths in this problem do not need to begin at the root or end at a leaf. This means paths can start and end anywhere in the tree as long as they go downwards.
The goal is to count all such unique paths that have a sum equal to the targetSum.

One of the main challenges is to consider all possible paths efficiently, including those that start and end in the middle of the tree.

Flowchart Walkthrough

Let's find the appropriate algorithm using the Flowchart. Here's a step-by-step analysis for Leetcode 437. Path Sum III:

Is it a graph?

Yes: The data structure is a binary tree, which can be visualized and treated as a type of graph.

Is it a tree?

Yes: The structure specified in the problem is explicitly a binary tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: Although a tree is a special kind of DAG, the problem itself is about finding the number of paths that sum to a given value, not about properties typically associated with DAGs like topological sorting.

Is the problem related to shortest paths?

No: We are not trying to find the shortest path; instead, we seek paths that sum to a specific value.

Does the problem involve connectivity?

No: The main focus is not on connectivity between nodes, but rather on summing values along paths.

Is the graph weighted?

No: While the tree nodes have values, the problem does not involve dealing with weights in the context of optimizing paths (like finding the shortest path). Each node has a value, but the structure is not considered "weighted" in the typical algorithmic sense that influences choices like Dijkstra's vs. BFS.

Conclusion: The flowchart leads us to the DFS strategy, suitable for traversing a tree and efficiently exploring all potential paths to check their sums against the target value.

Intuition

The intuition behind the solution involves a depth-first traversal of the tree while keeping track of the running sum of node values for each path traversed. Here's how we arrive at the solution:

We use a recursive depth-first search (dfs) method to explore all paths. Each time we visit a node, we add it to our current path's running sum.
To handle paths that start in the middle of the tree, we utilize a prefix sum technique. This involves keeping a count of the number of times each sum has occurred so far in the current path using a Counter (dictionary), which is updated as we go deeper into the tree.
For each node visited, we check if there's a previous sum that is exactly current_sum - targetSum. If such a sum exists, it means there's a subpath that sums to targetSum, and we increment our ans counter accordingly.
As we backtrack (after visiting a node's children), we decrement the count of the sum in our Counter to ensure that it only reflects sums for the current path.
By calling the dfs function starting from the root and an initial sum of 0, we traverse the entire tree, and our answer is aggregated through the ans counter.

The use of the prefix sum and Counter is what allows us to efficiently keep track of the number of valid paths without having to explicitly store every path's values.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The solution provided implements a Depth-First Search (DFS) algorithm using recursion. It uses a combination of techniques including the traversal method and the prefix sum count, which are integrated into a single pass through the binary tree. Here's a step-by-step explanation of the approach:

Definition: A helper function dfs(node, s) is defined, where node is the current node in the binary tree and s is the running sum of values from the root to this node.
Base Case: If node is None, meaning we have reached past a leaf, the function returns 0.
Running Sum Update: Add the current node's value to the running sum (i.e., s += node.val).
Prefix Sum Calculation: Check if the current running sum (s), minus the targetSum, exists as a key in the cnt dictionary, which is a Counter of prefix sums. If it does, that indicates there are paths that, when removed from the current path, yield a path that sums to targetSum (i.e., ans = cnt[s - targetSum]).
Updating the Prefix Sum Counter: Before continuing to child nodes, increment the count for the current sum in the cnt dictionary to reflect this sum has been reached.
Recursive DFS Calls: Perform DFS on the left and right children, if they exist, and add their results to our ans (i.e., ans += dfs(node.left, s) and ans += dfs(node.right, s)). This counts all paths from the child nodes downwards that sum to targetSum.
Backtracking: Once we have explored the current node's descendants, we decrement the prefix sum count (cnt[s] -= 1). This is to prevent the current path's sum from affecting other paths as we backtrack up the tree.
Returning the Result: The dfs function ultimately returns the count of all valid paths found (ans).
Initialization and Invocation: In the pathSum function, we initialize cnt = Counter({0: 1}). This is important because it accounts for the path that consists only of the node itself if the node's value equals targetSum. Then, we invoke dfs(root, 0) starting from the root with an initial sum of 0.

By using this approach, each possible path in the tree is considered exactly once, and we incrementally build up our understanding of how many times each prefix sum has been seen without needing to store entire paths or revisit nodes. The algorithm scales reasonably well as it visits each node only once, and prefix sum lookup and update operations are typically O(1) on average.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small binary tree example to illustrate the solution approach.

Consider the following binary tree where the target sum is 8:

       5
      / \
     4   8
    /   / \
   11  13  4
  / \      / \
 7   2    5   1

Let's walk through the dfs method applied to this tree:

Start the dfs with the root node (value 5) and an initial running sum s of 0. We initialize the counter dictionary cnt with one entry {0: 1} to account for any one-node path that might equal the targetSum.
At the root node (5), update running sum to s = 0 + 5 = 5. Since s - targetSum = 5 - 8 = -3 is not in cnt, no paths ending here sum to 8. Update cnt to {0: 1, 5: 1} and proceed.
Move to the left child (4), and s becomes 9. s - targetSum = 9 - 8 = 1 is not in cnt, so no paths ending here sum to 8 either. Update cnt to {0: 1, 5: 1, 9: 1}.
Move to the left child of 4, which is node 11, and update s to 20. s - targetSum = 20 - 8 = 12 is not in cnt. Update cnt to {0: 1, 5: 1, 9: 1, 20: 1}.
Now move to the left child of 11, which is 7, and s becomes 27. There's no prefix sum that makes s - targetSum equal to an existing key in cnt. Update cnt to {0: 1, 5: 1, 9: 1, 20: 1, 27: 1}.
Backtrack to 11 and then to its right child 2, making s equal to 22. Checking for s - targetSum gives us 22 - 8 = 14, which is not present in cnt. Update cnt and move up the tree as there are no more children, updating cnt at each step (removing counts for 27 and 22).
Now, we go down the right subtree following a similar process, until we reach the right child of 8, which is the node 4 on the right side. When we reach node 4, our running sum s is 5 + 8 + 4 = 17. Checking our cnt, we see that 17 - 8 = 9, and 9 is a key in our cnt with a value of 1 ({0: 1, 5: 1, 9: 1, ...}). This means we found a path sum (from 5 to 4 on the right) to 8. Increment our answer counter by 1.
Explore the left child of this 4 (node 5), and we get a running sum of 17 + 5 = 22. Now, 22 - 8 = 14 is not in cnt; thus, this does not form a path sum of 8. Proceed similarly with the right child (node 1).

By using this recursive approach, we traverse each path in the tree, update a running sum, check against our cnt to find valid paths, and backtrack accordingly. Once the whole tree is traversed, we would have counted all unique paths that sum to the given target sum of 8.

Solution Implementation

1from collections import Counter
2
3# Definition for a binary tree node.
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    def pathSum(self, root: Optional[TreeNode], target_sum: int) -> int:
12        # Helper function to perform depth-first search
13        def dfs(node, current_sum):
14            if node is None:
15                return 0
16            # Increment the current path's sum with the current node's value
17            current_sum += node.val
18          
19            # Number of times the (current_sum - target_sum) has occurred so far
20            # which indicates a valid path when subtracted from the current_sum
21            path_count = path_counts[current_sum - target_sum]
22          
23            # Store the current path's sum in the counter
24            path_counts[current_sum] += 1
25          
26            # Recursively find paths in left and right subtrees
27            path_count += dfs(node.left, current_sum)
28            path_count += dfs(node.right, current_sum)
29          
30            # Once the node is done, remove its sum from the counter
31            # to not use it in the parallel subtree calls
32            path_counts[current_sum] -= 1
33          
34            # Return the number of paths found
35            return path_count
36
37        # Initialize a counter to keep track of all path sums
38        path_counts = Counter({0: 1})
39      
40        # Call the dfs function from the root of the tree
41        return dfs(root, 0)
42

1class Solution {
2    // A map to store the cumulative sum up to all the ancestors of a node and their respective counts.
3    private Map<Long, Integer> cumulativeSumCount = new HashMap<>();
4    // The target sum to find in the path.
5    private int targetSum;
6
7    // Public function to call the private dfs function and initialize the cumulativeSumCount.
8    public int pathSum(TreeNode root, int targetSum) {
9        // Initialize the map with zero cumulative sum having a count of one.
10        cumulativeSumCount.put(0L, 1);
11        // Store the target sum in the global variable to use in the dfs function.
12        this.targetSum = targetSum;
13        // Start the DFS traversal.
14        return dfs(root, 0);
15    }
16
17    // A private function to perform the DFS traversal and find paths with sums equal to targetSum.
18    private int dfs(TreeNode node, long currentSum) {
19        // Base case: If the current node is null, return 0 as there are no paths through this node.
20        if (node == null) {
21            return 0;
22        }
23        // Add the current node's value to the cumulative sum.
24        currentSum += node.val;
25        // Find the number of paths that end at this node with a sum equal to targetSum.
26        int pathCount = cumulativeSumCount.getOrDefault(currentSum - targetSum, 0);
27        // Update the map with the new cumulative sum, incrementing its count by 1.
28        cumulativeSumCount.merge(currentSum, 1, Integer::sum);
29        // Recursively call dfs for the left child.
30        pathCount += dfs(node.left, currentSum);
31        // Recursively call dfs for the right child.
32        pathCount += dfs(node.right, currentSum);
33        // After the children have been processed, decrement the count of the currentSum
34        // path count because it should not be counted in other paths.
35        cumulativeSumCount.merge(currentSum, -1, Integer::sum);
36        // Return the total count of valid paths found from this node.
37        return pathCount;
38    }
39}
40
41// Definition for a binary tree node.
42class TreeNode {
43    int val;
44    TreeNode left;
45    TreeNode right;
46
47    TreeNode() {}
48
49    TreeNode(int val) { this.val = val; }
50
51    TreeNode(int val, TreeNode left, TreeNode right) {
52        this.val = val;
53        this.left = left;
54        this.right = right;
55    }
56}
57

1#include <unordered_map>
2#include <functional>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode() : val(0), left(nullptr), right(nullptr) {}
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    int pathSum(TreeNode* root, int targetSum) {
17        // Counter to store the prefix sum frequencies
18        std::unordered_map<long long, int> prefixSumCounter;
19        // Initialize the counter with sum 0 and frequency 1
20        prefixSumCounter[0] = 1;
21
22        // Recursive lambda function that performs DFS traversal
23        std::function<int(TreeNode*, long long)> dfs = [&](TreeNode* node, long long currentSum) -> int {
24            if (!node) return 0;  // Base case: if the node is null, return 0
25
26            currentSum += node->val; // Update the current sum by adding the node's value
27            // Determine the number of paths with sum (currentSum - targetSum)
28            int numPaths = prefixSumCounter[currentSum - targetSum];
29            // Increment the count of paths equal to the current sum
30            ++prefixSumCounter[currentSum];
31            // Recur on the left and right subtrees to find more paths and add to numPaths
32            numPaths += dfs(node->left, currentSum) + dfs(node->right, currentSum);
33            // Decrement the count back as we backtrack, ensuring the current
34            // path's sum does not affect other paths
35            --prefixSumCounter[currentSum];
36
37            return numPaths; // Return the total number of valid paths found
38        };
39
40        // Kickstart the DFS from the root with an initial sum of `0`
41        return dfs(root, 0);
42    }
43};
44

1// Represents a node in the binary tree.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8        this.val = val === undefined ? 0 : val;
9        this.left = left === undefined ? null : left;
10        this.right = right === undefined ? null : right;
11    }
12}
13
14// Function to calculate the number of paths that sum to a given value.
15function pathSum(root: TreeNode | null, targetSum: number): number {
16    // Map to keep the cumulative sum and its frequency.
17    const prefixSumCount: Map<number, number> = new Map();
18
19    // Helper function to perform DFS on the tree and calculate paths.
20    const dfs = (node: TreeNode | null, currentSum: number): number => {
21        if (!node) {
22            return 0;
23        }
24        // Update the current sum by adding the node's value.
25        currentSum += node.val;
26
27        // Get the number of times we have seen the currentSum - targetSum.
28        let pathCount = prefixSumCount.get(currentSum - targetSum) || 0;
29
30        // Update the count of the current sum in the map.
31        prefixSumCount.set(currentSum, (prefixSumCount.get(currentSum) || 0) + 1);
32
33        // Explore left and right subtrees.
34        pathCount += dfs(node.left, currentSum);
35        pathCount += dfs(node.right, currentSum);
36
37        // After returning from the recursion, decrement the frequency of the current sum.
38        prefixSumCount.set(currentSum, (prefixSumCount.get(currentSum) || 0) - 1);
39
40        // Return the total count of paths found.
41        return pathCount;
42    };
43
44    // Initialize the map with base case before the recursion.
45    prefixSumCount.set(0, 1);
46
47    // Start DFS from the root node with an initial sum of 0.
48    return dfs(root, 0);
49}
50

Time and Space Complexity

Time Complexity

The time complexity of the given DFS (Depth-First Search) algorithm is O(N), where N is the number of nodes in the binary tree. Here's why:

The algorithm visits each node exactly once. At each node, it does a constant amount of work, primarily updating the cnt dictionary and calculating the ans.
The recursion stack could go as deep as the height of the tree, but since the function visits all N nodes once, the total amount of work done is proportional to the number of nodes, which is O(N).

Space Complexity

The space complexity of the algorithm consists of two parts: the recursion stack space and the space used by the cnt dictionary.

Recursion Stack Space: In the worst-case scenario, the binary tree could be skewed (e.g., a linked-list shaped tree), which would mean that the recursion depth could be N. Therefore, the space complexity for recursion would be O(N).
cnt Dictionary Space: The cnt dictionary can contain at most one entry for every prefix sum encountered during the DFS traversal. In the worst case, the number of unique prefix sums could be O(N).

Combining both, the overall space complexity of the algorithm is O(N), where N is the number of nodes in the tree. This takes into account the space for the recursion stack and the space for the cnt dictionary.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

BFS

DFS

Both

Neither

I don’t know