LeetCode 113: Path Sum II

Problem Restatement

We are given the root of a binary tree and an integer targetSum.

We need to return all root-to-leaf paths where the sum of node values equals targetSum.

Each returned path must:

1. Start at the root.
2. End at a leaf.
3. Have node values summing to targetSum.

The official problem asks for all root-to-leaf paths whose sum equals the target. (leetcode.com)

For this tree:

        5
      /   \
     4     8
    /     / \
   11    13  4
  /  \      / \
 7    2    5   1

and:

targetSum = 22

The valid paths are:

[
    [5, 4, 11, 2],
    [5, 8, 4, 5]
]

Input and Output

LeetCode gives the TreeNode class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The function shape is:

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> list[list[int]]:
        ...

Examples

Consider:

        5
      /   \
     4     8
    /     / \
   11    13  4
  /  \      / \
 7    2    5   1

with:

targetSum = 22

One root-to-leaf path is:

5 -> 4 -> 11 -> 2

Its sum is:

22

Another valid path is:

5 -> 8 -> 4 -> 5

Its sum is also:

22

So the answer is:

[
    [5, 4, 11, 2],
    [5, 8, 4, 5]
]

Now consider:

   1
  / \
 2   3

with:

targetSum = 5

The root-to-leaf paths are:

1 -> 2 = 3
1 -> 3 = 4

No path sums to 5, so the answer is:

[]

First Thought: Explore Every Root-to-Leaf Path

This problem is similar to LeetCode 112.

We still need to explore all root-to-leaf paths.

The difference is:

• LeetCode 112 asks whether at least one valid path exists.
• This problem asks us to return every valid path.

That means we must keep track of the current path while doing DFS.

Key Insight

During DFS, maintain:

1. The current path.
2. The remaining sum.

At each node:

• Add the node value to the path.
• Subtract the node value from the remaining target.

When we reach a leaf:

• If the remaining target equals the leaf value, store a copy of the current path.

After exploring a subtree, remove the current node from the path before returning.

This removal step is called backtracking.

Without backtracking, values from one branch would incorrectly remain in the path for another branch.

Algorithm

Create:

ans = []
path = []

Define a recursive DFS function.

For each node:

1. If the node is None, return.
2. Add the node value to path.
3. If the node is a leaf:
   1. Check whether the path sum matches the target.
   2. If yes, append a copy of path to ans.
4. Otherwise:
   1. Continue DFS into the left subtree.
   2. Continue DFS into the right subtree.
5. Remove the current node from path.

The recursive calls use:

remaining - node.val

Correctness

The DFS explores every root-to-leaf path exactly once.

At each recursive call, path contains exactly the node values from the root to the current node, in order. The variable remaining stores the target sum still needed from the current node downward.

When the algorithm reaches a leaf, the current path is complete. If the remaining target equals the leaf value, then the sum of all values in path equals targetSum, so the path is valid and is added to the answer list.

The recursive calls explore both left and right subtrees, so no possible root-to-leaf path is missed.

After finishing a subtree, the algorithm removes the current node from path. Therefore, the path state is restored correctly before exploring another branch. This guarantees that paths from different branches do not interfere with each other.

Thus, every valid root-to-leaf path is added exactly once, and no invalid path is included.

Complexity

Here:

• n is the number of nodes.
• h is the tree height.

Copying valid paths costs additional time proportional to path length.

Implementation

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) -> list[list[int]]:
        ans = []
        path = []

        def dfs(node: Optional[TreeNode], remaining: int) -> None:
            if node is None:
                return

            path.append(node.val)

            if node.left is None and node.right is None:
                if remaining == node.val:
                    ans.append(path[:])
            else:
                dfs(node.left, remaining - node.val)
                dfs(node.right, remaining - node.val)

            path.pop()

        dfs(root, targetSum)

        return ans

Code Explanation

The answer list stores all valid paths:

ans = []

The path list stores the current DFS path:

path = []

The DFS helper receives:

node
remaining

Handle the empty subtree:

if node is None:
    return

Add the current node to the path:

path.append(node.val)

Check whether the current node is a leaf:

if node.left is None and node.right is None:

If the remaining target equals the current value, the path is valid:

if remaining == node.val:
    ans.append(path[:])

path[:] creates a copy.

Without copying, later modifications would change stored answers.

For non-leaf nodes, continue DFS:

dfs(node.left, remaining - node.val)
dfs(node.right, remaining - node.val)

Finally, remove the current node before returning:

path.pop()

This restores the path for the parent call.

Testing

from typing import Optional

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) -> list[list[int]]:
        ans = []
        path = []

        def dfs(node: Optional[TreeNode], remaining: int) -> None:
            if node is None:
                return

            path.append(node.val)

            if node.left is None and node.right is None:
                if remaining == node.val:
                    ans.append(path[:])
            else:
                dfs(node.left, remaining - node.val)
                dfs(node.right, remaining - node.val)

            path.pop()

        dfs(root, targetSum)

        return ans

def run_tests():
    s = Solution()

    root1 = TreeNode(
        5,
        TreeNode(
            4,
            TreeNode(11, TreeNode(7), TreeNode(2)),
        ),
        TreeNode(
            8,
            TreeNode(13),
            TreeNode(4, TreeNode(5), TreeNode(1)),
        ),
    )

    assert sorted(s.pathSum(root1, 22)) == sorted([
        [5, 4, 11, 2],
        [5, 8, 4, 5],
    ])

    root2 = TreeNode(1, TreeNode(2), TreeNode(3))
    assert s.pathSum(root2, 5) == []

    root3 = None
    assert s.pathSum(root3, 0) == []

    root4 = TreeNode(1)
    assert s.pathSum(root4, 1) == [[1]]

    root5 = TreeNode(
        -2,
        None,
        TreeNode(-3),
    )
    assert s.pathSum(root5, -5) == [[-2, -3]]

    print("all tests passed")

run_tests()

Test meaning: