Path Sum III – LeetCode75 Python Solution Explained

The Path Sum III problem (LeetCode75) is a classic binary tree challenge that evaluates your ability to traverse trees, track running sums and use hashmaps for efficient counting. This problem is popular in coding interviews because it tests recursion, prefix sums and path tracking in trees.

In this blog, we’ll explain the problem, provide Python solutions, step-by-step explanations with code snippets, time and space complexity analysis and real-world applications.

Problem Statement

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

Important Notes:

The path does not need to start or end at the root or a leaf.
The path must go downwards (traveling only from parent nodes to child nodes).

Example 1

Input:

root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

Output:

Explanation:
The paths that sum to 8 are:

5 → 3
5 → 2 → 1
-3 → 11

Example 2

Input:

root = [1,null,2,null,3,null,4,null,5], targetSum = 3

Output:

Explanation:
The paths that sum to 3 are:

1 → 2
3

Understanding the Problem

Key points:

The path can start and end anywhere as long as it moves downward.
A prefix sum hashmap is used to track running sums and efficiently count paths.
This approach avoids checking all possible paths, reducing time complexity from O(n²) to O(n).

Complete Python Solution

from typing import Optional

# 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, current_sum, path_sums):
            if not node:
                return 0
            
            current_sum += node.val
            count = path_sums.get(current_sum - targetSum, 0)
            path_sums[current_sum] = path_sums.get(current_sum, 0) + 1

            count += dfs(node.left, current_sum, path_sums)
            count += dfs(node.right, current_sum, path_sums)

            path_sums[current_sum] -= 1

            return count
        
        return dfs(root, 0, {0:1})

Step-by-Step Explanation

Step 1: Initialize DFS and Path Sums

We traverse the tree recursively using DFS while keeping a hashmap path_sums to store prefix sums and their frequency.

path_sums = {0: 1}  # Base case: zero sum occurs once

Step 2: Update Current Sum

For each node, add its value to the current running sum.

current_sum += node.val

Step 3: Count Paths Ending at Current Node

Check if current_sum - targetSum exists in path_sums. If yes, it means there’s a path ending at the current node that sums to targetSum.

count = path_sums.get(current_sum - targetSum, 0)

Step 4: Add Current Sum to Path Sums

Increment the count of current_sum in the hashmap.

path_sums[current_sum] = path_sums.get(current_sum, 0) + 1

Step 5: Recur for Left and Right Subtrees

count += dfs(node.left, current_sum, path_sums)
count += dfs(node.right, current_sum, path_sums)

Step 6: Backtrack

After visiting left and right subtrees, decrement the count of current_sum to backtrack and ensure other paths are counted correctly.

path_sums[current_sum] -= 1

Step 7: Return Total Count

Return the total number of paths that sum to targetSum.

return count

Time and Space Complexity

Time Complexity: O(n) – Each node is visited once.
Space Complexity: O(n) – Hashmap stores prefix sums and recursion stack can go up to the height of the tree.

Edge Cases

Empty Tree: No nodes → return 0.
All Node Values Zero: Multiple paths can sum to zero.
Negative Values: Handled correctly with prefix sums.
Single Node Tree: Check if the node’s value equals targetSum.

Real-World Applications

Financial Analytics: Finding cumulative sums in hierarchical transaction data.
Gaming Trees: Detecting paths with exact resource accumulation.
Hierarchical Data Analysis: Counting paths with a target metric in organizational trees.
Algorithm Optimization: Learning prefix sum techniques in recursion.

Conclusion

The Path Sum III problem is an excellent exercise in combining DFS traversal, prefix sums and recursion. By using a hashmap to track running sums, you can efficiently count all paths that sum to a target even when paths start and end at arbitrary nodes.

Mastering this problem improves your understanding of:

Recursive tree traversal
Prefix sum optimization
Backtracking in DFS
Handling edge cases in binary trees