Path Sum III Python Solution with Tests

Tested Python solution for LeetCode 437 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 437, Medium. Topics: Tree, Depth-First Search, Binary Tree. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 437   # by problem number
lcpy gen -s path_sum_iii   # by problem name

​

Problem

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.

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

​

Examples

Input: root = [10,5,-3,3,2,None,11,3,-2,None,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Input: root = [5,4,8,11,None,13,4,7,2,None,None,5,1], targetSum = 22
Output: 3

​

Constraints

• The number of nodes in the tree is in the range [0, 1000].
• -10^9 <= Node.val <= 10^9
• -1000 <= targetSum <= 1000

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import defaultdict

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(n)
    def path_sum(self, root: TreeNode[int] | None, target_sum: int) -> int:
        """Count paths where sum equals target_sum using prefix sum technique."""
        self.count = 0
        prefix_counts: defaultdict[int, int] = defaultdict(int)
        prefix_counts[0] = 1  # Empty path prefix

        def dfs(node: TreeNode[int] | None, current_sum: int) -> None:
            if not node:
                return

            current_sum += node.val
            # Check if (current_sum - target_sum) exists in prefix_counts
            self.count += prefix_counts[current_sum - target_sum]
            # Add current sum to prefix_counts
            prefix_counts[current_sum] += 1

            # Recurse on children
            dfs(node.left, current_sum)
            dfs(node.right, current_sum)

            # Backtrack: remove current sum from prefix_counts
            prefix_counts[current_sum] -= 1

        dfs(root, 0)
        return self.count

​

Complexity

Time	Space
O(n)	O(n)

​

Tags

Grind, AlgoMaster 75.