Problem Statement

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Examples

Example 1

Example 2

Example 3

Solution

Points of Interest

To simplify the solution, we can break down this problem as follows

1. At the root we ask: give me a pth from this tree that has sum equal to target sum
2. Go to its children and ask the same question but now the target sum will be (actual target sum minus the value of the root)
3. We can keep doing that on each node until we reach a leaf node. There, we check if the target sum minus the value of that leaf node equals 0, if so, we have found a path; otherwise, we haven’t.
4. We should keep in mind that target sum as well as node values can be negative
5. This is important as it’s possible that a sum might become 0 at a non leaf node but its still possible that sum might be 0 in some path going through it.

Algo

We will use recursion to solve this problem.

1. Create a method _pathSum which will accept following non optional parameters:
   1. A $root$ of the current sub-tree
   2. $target\_sum$ required from that sub-tree
   3. $path\_array$ for path traveled from root to this node so far
   4. $results$ an array that holds the valid paths seen so far
2. In this function do following
3. Save $(targetSum - root.val)$ in variable $new\_sum$
4. Append $root.val$ into $path\_array$
5. If $new\_sum$ is 0 and root is a leaf node
   1. Append a copy of $path\_array$ into $results$ (We are copying it because $path\_array$ is a shared variable across recursion)
6. Else
   1. If root has a left node, call $\_pathSum$ with its left node and $new\_sum$
   2. If root has a right node, call $\_pathSum$ with its right node and $new\_sum$
7. Remove last value from $path\_array$ to keep $path\_array$ clean for parent recursive calls

At the end of the recursion calls, results will have all paths that satisfy our criteria.

Code

def _pathSum(root: TreeNode, targetSum: int, path_array: list[int], results: list[list[int]]):
    new_sum = targetSum - root.val
    path_array.append(root.val)
    if new_sum == 0 and not root.left and not root.right:
        results.append(path_array.copy())
    else:
        if root.left:
            _pathSum(root.left, new_sum, path_array, results)
        if root.right:
            _pathSum(root.right, new_sum, path_array, results)
    path_array.pop()

def pathSum(root: Optional[TreeNode], targetSum: int) -> list[list[int]]:
    if not root:
        return list()
    
    results = list()
    _pathSum(root, targetSum, [], results)
    return results

Complexity

$\textbf{Time Complexity} = O(N) \text{ where N is number of nodes in binary tree}$

• We are visiting each node only once
• For each node visit we have finite number of computations or i/o steps executed

$\textbf{Space Complexity} = O(H) \text{ where H is height of the binary tree}$

• This excludes the size of array which cannot be optimized no matter what
• We are storing $path\_array$ that can contain max H elements
• Other than that there will be stack memory used due to recursion. This will be max up to H with finite number of variables each