#437

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Path Sum III

Path Sum III challenges you to count paths in a binary tree that sum to a given target value with downward traversal.

Problem Statement

Given a binary tree's root and a target sum, count the number of paths where the sum of the values along the path equals the target. These paths do not necessarily start or end at the root or leaves, but must always traverse downward through parent-child relationships.

For example, with root = [10,5,-3,3,2,null,11,3,-2,null,1] and targetSum = 8, there are 3 paths that sum to 8. The paths are 5->3, 3->2->3, and -3->11.

Examples

Example 1

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

Output: 3

The paths that sum to 8 are shown.

Example 2

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

Output: 3

Example details omitted.

Constraints

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

Solution Approach

Depth-First Search (DFS) with State Tracking

A DFS approach is used to traverse the tree from each node, while tracking the cumulative sum along the current path. Whenever the sum matches the target, a valid path is counted.

Prefix Sum Approach

Another efficient way to solve the problem is by using a prefix sum and hash map to track the cumulative sum up to each node. This helps to check if a previous sum exists that, when subtracted from the current sum, equals the target.

Recursive DFS with Memoization

You can optimize the solution by storing the results of previously computed subproblems using memoization. This helps avoid redundant calculations and speeds up the process when exploring similar paths multiple times.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the specific approach, but the DFS method generally works in O(N) time, where N is the number of nodes in the tree. The space complexity depends on the stack used in DFS or the hash map in the prefix sum approach, typically O(N) as well.

What Interviewers Usually Probe

Can the candidate implement DFS with state tracking or prefix sums to handle path sum?
How well does the candidate optimize for memory usage and performance?
Does the candidate demonstrate awareness of potential edge cases, such as empty trees or negative values?

Common Pitfalls or Variants

Common pitfalls

Failing to account for paths that don’t start at the root or end at a leaf.
Inefficient traversal that results in redundant calculations without optimization.
Not considering negative values in the tree, which can affect the sum calculations.

Follow-up variants

Handling binary trees with negative node values.
Adapting the algorithm to find paths with sums greater than or less than the target.
Extending the problem to count paths of a fixed length or with additional constraints.

FAQ

What is the main approach to solving Path Sum III?

The primary approach is depth-first search (DFS) with state tracking, optionally enhanced with a prefix sum or memoization to improve efficiency.

What are common mistakes in Path Sum III?

Common mistakes include not handling paths that don't start or end at the root or leaves, inefficient traversal, and overlooking negative node values.

Can Path Sum III be solved using a brute force method?

Yes, but it is highly inefficient. A brute force approach would involve checking all paths individually, leading to an O(N^2) time complexity.

How do you optimize the solution for Path Sum III?

Optimizations include using a prefix sum with a hash map to track sums efficiently and applying DFS with memoization to avoid redundant calculations.

What is the space complexity of Path Sum III?

The space complexity depends on the method used. For DFS, it's O(N), and for the prefix sum approach, it could also be O(N) due to the hash map.

terminal

Solution

Solution 1: Hash Table + Prefix Sum + Recursion

We can use the idea of prefix sums to recursively traverse the binary tree while using a hash table $\textit{cnt}$ to count the occurrences of each prefix sum along the path from the root to the current node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# 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, s):
            if node is None:
                return 0
            s += node.val
            ans = cnt[s - targetSum]
            cnt[s] += 1
            ans += dfs(node.left, s)
            ans += dfs(node.right, s)
            cnt[s] -= 1
            return ans

        cnt = Counter({0: 1})
        return dfs(root, 0)

Continue Practicing

#449 serialize and deserialize bst #404 sum of left leaves #501 find mode in binary search tree