Problem Description

You are given the root of a binary tree and an integer targetSum. Your task is to find the number of paths in the tree where the sum of node values along the path equals targetSum.

The path must follow these rules:

• It can start at any node in the tree (not necessarily the root)
• It can end at any node in the tree (not necessarily a leaf)
• It must go downwards, meaning you can only travel from parent nodes to child nodes

The solution uses a clever combination of prefix sums and hash tables. As we traverse the tree using DFS, we maintain a running sum s from the root to the current node. The key insight is that if we want to find a path ending at the current node with sum equal to targetSum, we need to check if there exists a prefix sum equal to s - targetSum somewhere along the path from root to the current node.

The algorithm works as follows:

1. We maintain a hash table cnt that stores the frequency of each prefix sum encountered along the current path
2. Initialize cnt with {0: 1} to handle paths starting from the root
3. For each node, we calculate the prefix sum s and check how many times s - targetSum appears in our hash table - this gives us the number of valid paths ending at the current node
4. We add the current prefix sum to the hash table before recursing to children
5. After processing both children, we remove the current prefix sum from the hash table (backtracking) to ensure it doesn't affect other branches

The time complexity is O(n) where n is the number of nodes, as we visit each node once. The space complexity is O(h) where h is the height of the tree, needed for the recursion stack and the hash table storing at most h prefix sums at any time.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a binary tree, which is a special type of graph with nodes (tree nodes) and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where we need to traverse from parent nodes to child nodes.

DFS

• We arrive at DFS: Since we're dealing with a tree and need to explore paths from any node to any descendant node, DFS is the appropriate choice. DFS allows us to:
  • Traverse the tree systematically
  • Keep track of the current path from root to the current node
  • Process each node while maintaining the context of its ancestors
  • Backtrack efficiently when exploring different branches

Conclusion: The flowchart correctly leads us to use DFS (Depth-First Search) for Path Sum III. This makes sense because:

1. We need to explore all possible paths in the tree
2. Each path must go downward (parent to child), which naturally fits DFS traversal
3. We need to maintain information about the current path (prefix sums), which DFS handles well with its recursive nature
4. The backtracking aspect of DFS helps us efficiently manage the prefix sum counts when moving between different branches of the tree

Intuition

The key insight comes from recognizing that this is a subarray sum problem in disguise, just mapped onto a tree structure instead of an array.

Think about it this way: if we had an array and wanted to find all subarrays with sum equal to targetSum, we could use the prefix sum technique. For any index j, if we know the prefix sum up to j is currentSum, and somewhere earlier at index i the prefix sum was currentSum - targetSum, then the subarray from i+1 to j has sum equal to targetSum.

Now, how do we adapt this to a tree? In a tree, instead of a linear array, we have multiple paths from the root to various nodes. As we traverse down using DFS, we're essentially creating a temporary "array" - the path from root to the current node.

Here's the breakthrough: while traversing with DFS, we can treat the current path as if it were an array and apply the prefix sum technique.

For each node we visit:

1. We maintain the cumulative sum from root to this node
2. We check: "Have I seen a prefix sum of currentSum - targetSum anywhere along this path?" If yes, that means there's a valid path ending at the current node
3. We record our current prefix sum for future nodes to reference

The clever part is the backtracking - when we finish exploring a subtree and return to the parent, we need to "forget" the prefix sum we added. Why? Because when we explore the sibling subtree, that prefix sum from the first subtree shouldn't be available (they're on different paths from root).

This is why we increment cnt[s] before recursing to children and decrement it after - we're essentially saying "this prefix sum is only valid for paths that go through the current node."

The initialization cnt = {0: 1} handles the edge case where a path starting from the root itself has sum equal to targetSum.

Solution Approach

Let's walk through the implementation step by step, building on our prefix sum intuition:

Data Structures Used:

• Hash Table (Counter): Stores the frequency of each prefix sum along the current path from root to the current node
• Recursive DFS: Traverses the tree while maintaining the running sum

Implementation Details:

1. Initialize the Hash Table:

   cnt = Counter({0: 1})

   We start with {0: 1} to handle paths that start from the root and have sum equal to targetSum. This is crucial - if we reach a node where the prefix sum equals targetSum, then s - targetSum = 0, and we need cnt[0] to be 1 to count this path.

2. DFS Function Design:

   def dfs(node, s):

   • node: Current node being processed
   • s: Prefix sum from root to the parent of the current node
   • Returns: Number of valid paths in the subtree rooted at node

3. Calculate Current Prefix Sum:

   s += node.val

   Update the prefix sum to include the current node's value.

4. Count Valid Paths Ending at Current Node:

   ans = cnt[s - targetSum]

   If there exists a prefix sum equal to s - targetSum somewhere along the path from root, then the subpath from that point to the current node has sum equal to targetSum. The value cnt[s - targetSum] gives us the count of all such valid paths.

5. Update Hash Table Before Recursion:

   cnt[s] += 1

   Add the current prefix sum to our hash table so that nodes in the subtree can use it to find valid paths.

6. Recursive Exploration:

   ans += dfs(node.left, s)
   ans += dfs(node.right, s)

   Recursively explore left and right subtrees, accumulating the count of valid paths from each.

7. Backtrack - Remove Current Prefix Sum:

   cnt[s] -= 1

   This is the crucial backtracking step. Once we've finished exploring the current node's subtree, we remove its prefix sum from the hash table. This ensures that when we explore other branches of the tree, they won't incorrectly use this prefix sum (since they're on different paths from root).

Why This Works:

The algorithm maintains an invariant: at any point during the traversal, cnt contains exactly the prefix sums along the current path from root to the current node. This allows us to correctly identify all valid subpaths ending at each node while avoiding false positives from other branches.

Time and Space Complexity:

• Time: O(n) where n is the number of nodes, as we visit each node exactly once
• Space: O(h) where h is the height of the tree, needed for:
  • Recursion stack: O(h)
  • Hash table: At most O(h) entries (one per level in the current path)

Example Walkthrough

Let's walk through a concrete example to see how the prefix sum approach works on a binary tree.

Consider this binary tree with targetSum = 8:

        10
       /  \
      5    -3
     / \     \
    3   2     11
   / \   \
  3  -2   1

Let's trace through the DFS traversal, focusing on how we find paths summing to 8:

Initial State:

• cnt = {0: 1} (to handle paths starting from root)
• Start DFS at root (10)

Step 1: Visit node 10

• Prefix sum s = 0 + 10 = 10
• Check: cnt[10 - 8] = cnt[2] = 0 (no paths ending here)
• Update: cnt = {0: 1, 10: 1}
• Recurse to left child (5)

Step 2: Visit node 5

• Prefix sum s = 10 + 5 = 15
• Check: cnt[15 - 8] = cnt[7] = 0 (no paths ending here)
• Update: cnt = {0: 1, 10: 1, 15: 1}
• Recurse to left child (3)

Step 3: Visit node 3

• Prefix sum s = 15 + 3 = 18
• Check: cnt[18 - 8] = cnt[10] = 1 ✓ Found path: 5→3 = 8
• Update: cnt = {0: 1, 10: 1, 15: 1, 18: 1}
• Recurse to left child (3)

Step 4: Visit node 3 (leaf)

• Prefix sum s = 18 + 3 = 21
• Check: cnt[21 - 8] = cnt[13] = 0 (no paths ending here)
• Update: cnt = {0: 1, 10: 1, 15: 1, 18: 1, 21: 1}
• No children, backtrack: cnt[21] -= 1

Step 5: Back at node 3, visit right child (-2)

• Prefix sum s = 18 + (-2) = 16
• Check: cnt[16 - 8] = cnt[8] = 0 (no paths ending here)
• Update: cnt = {0: 1, 10: 1, 15: 1, 18: 1, 16: 1}
• No children, backtrack: cnt[16] -= 1

Step 6: Back at node 3, finished both children

• Backtrack: cnt[18] -= 1
• cnt = {0: 1, 10: 1, 15: 1}

Step 7: Back at node 5, visit right child (2)

• Prefix sum s = 15 + 2 = 17
• Check: cnt[17 - 8] = cnt[9] = 0 (no paths ending here)
• Update: cnt = {0: 1, 10: 1, 15: 1, 17: 1}
• Recurse to right child (1)

Step 8: Visit node 1

• Prefix sum s = 17 + 1 = 18
• Check: cnt[18 - 8] = cnt[10] = 1 ✓ Found path: 5→2→1 = 8
• Update: cnt = {0: 1, 10: 1, 15: 1, 17: 1, 18: 1}
• No children, backtrack: cnt[18] -= 1

Continuing the traversal...

The process continues similarly for the right subtree. Notice how:

1. When we backtrack from node 5, we remove its prefix sum (15) from cnt
2. This ensures that when we explore node -3's subtree, we won't incorrectly use the prefix sum from node 5's path

Key Observations:

• The hash table cnt always contains only the prefix sums along the current path from root
• When we found the path 5→3, it was because at node 3 (with prefix sum 18), we found that cnt[10] = 1, meaning there was a node with prefix sum 10 earlier in the path
• The difference 18 - 10 = 8 equals our target, confirming the path from after node 10 to node 3 sums to 8
• Backtracking ensures we don't mix up paths from different branches

In total, this example would find paths like:

• 5 → 3 (sum = 8)
• 5 → 2 → 1 (sum = 8)
• -3 → 11 (sum = 8)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node is visited exactly once during the traversal. At each node, the following operations are performed:

• Adding the node's value to the current sum: O(1)
• Looking up cnt[s - targetSum]: O(1) average case for dictionary lookup
• Updating cnt[s] by incrementing: O(1) average case for dictionary update
• Recursive calls to left and right children
• Decrementing cnt[s]: O(1) average case for dictionary update

Since each of the n nodes is visited once and performs O(1) operations, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity consists of:

• Recursion call stack: In the worst case (skewed tree), the depth of recursion can be O(n). In a balanced tree, it would be O(log n).
• HashMap (Counter) cnt: In the worst case, the HashMap stores a unique prefix sum for each node along the current path from root to leaf. The maximum size would be the height of the tree, which is O(n) in the worst case.

Taking the worst-case scenario where the tree is completely unbalanced (like a linked list), both the recursion stack and the HashMap can grow to O(n), resulting in an overall space complexity of O(n).

Common Pitfalls

1. Forgetting to Initialize the Hash Table with {0: 1}

The Pitfall: Many people forget to initialize the hash table with {0: 1} and start with an empty hash table instead. This causes the algorithm to miss paths that start from the root node itself.

Why It Happens: When a path from the root to the current node has a sum exactly equal to targetSum, we need to check for current_sum - targetSum = 0 in our hash table. Without the initial {0: 1}, these valid paths won't be counted.

Example:

Tree:     10
         /  \
        5    -3
       / \     \
      3   2     11
     / \   \
    3  -2   1

targetSum = 8

The path 10 -> -3 -> 11 sums to 18. When at node 11, current_sum = 18. We check for 18 - 8 = 10 in our hash table. But also, the path 10 -> 5 -> 3 sums to 18, and when at the second 3, current_sum = 18. Without {0: 1}, we'd miss counting the path starting from root.

Incorrect Code:

# Wrong initialization
prefix_sum_count = Counter()  # Missing {0: 1}

Correct Code:

# Correct initialization
prefix_sum_count = Counter({0: 1})

2. Forgetting to Backtrack (Remove Prefix Sum After Processing)

The Pitfall: Failing to remove the current prefix sum from the hash table after processing both children leads to incorrect counts. The hash table would contain prefix sums from other branches, causing false positives.

Why It Happens: The hash table should only contain prefix sums along the current path from root to the current node. If we don't remove a prefix sum after processing a subtree, it remains available for nodes in completely different branches.

Example:

Tree:      1
          / \
         2   3
        /
       4

targetSum = 3

When processing node 4, the prefix sum is 7 (1+2+4). If we don't remove this from the hash table before processing node 3, node 3 might incorrectly use this prefix sum even though nodes 2 and 4 are not on the path to node 3.

Incorrect Code:

def dfs(node, current_sum):
    if node is None:
        return 0
  
    current_sum += node.val
    path_count = prefix_sum_count[current_sum - targetSum]
    prefix_sum_count[current_sum] += 1
  
    path_count += dfs(node.left, current_sum)
    path_count += dfs(node.right, current_sum)
  
    # Missing backtracking step!
    return path_count

Correct Code:

def dfs(node, current_sum):
    if node is None:
        return 0
  
    current_sum += node.val
    path_count = prefix_sum_count[current_sum - targetSum]
    prefix_sum_count[current_sum] += 1
  
    path_count += dfs(node.left, current_sum)
    path_count += dfs(node.right, current_sum)
  
    # Critical backtracking step
    prefix_sum_count[current_sum] -= 1
  
    return path_count

3. Using the Hash Table After Backtracking

The Pitfall: Some implementations mistakenly try to use the prefix sum after it has been removed from the hash table during backtracking.

Why It Happens: Confusion about the order of operations - the prefix sum must be removed only after all computations for the current node and its subtrees are complete.

Incorrect Code:

def dfs(node, current_sum):
    if node is None:
        return 0
  
    current_sum += node.val
    prefix_sum_count[current_sum] += 1
  
    # Backtracking too early!
    prefix_sum_count[current_sum] -= 1
  
    # This will always be 0 because we just removed the current sum
    path_count = prefix_sum_count[current_sum - targetSum]
  
    path_count += dfs(node.left, current_sum)
    path_count += dfs(node.right, current_sum)
  
    return path_count

Correct Order:

1. Update current sum
2. Count valid paths ending at current node
3. Add current sum to hash table
4. Process children recursively
5. Remove current sum from hash table (backtrack)
6. Return the total count