Path Sum II

35 min · pathSum()

A delivery route only counts when it reaches a destination. A promising subtotal halfway down the map isn't enough.

You're given the root of a binary tree and an integer targetSum. A root-to-leaf path starts at the root, follows child links, and stops at a node with no children. Return every such path whose node values add up to targetSum. Put the root value first and the leaf value last in each returned array.

A few ground rules:

The outer list may contain the matching paths in any order.
The values inside each path must stay in root-to-leaf order.
A sum reached at a node that still has a child doesn't count.
Return [] when the tree is empty or no complete path matches.

Constraints

0 <= node count <= 5_000
-1_000 <= node.val <= 1_000
-100_000_000 <= targetSum <= 100_000_000

Hints

Carry the subtotal

As you move from a parent to a child, add the child's value to one running sum. You don't need to add the whole path again at every node.

A match needs a leaf

Check the target only when both child links are empty. That condition prevents a matching prefix from sneaking into the answer.

Undo before the sibling

Use depth-first search (DFS), which follows one branch before returning to try another. Append when you enter a node, copy the list when a leaf matches, then remove the node before exploring a different branch.

Follow-up

Can you keep only one working path instead of copying every partial path along the way?

Visible cases

Examples

Example 1

ready

Input: root = [ 5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1 ] targetSum = 22
Expected: [ [ 5, 4, 11, 2 ], [ 5, 8, 4, 5 ] ]
Why: two different leaves complete a sum of 22

Example 2

ready

Input: root = [ 1, 2, 3 ] targetSum = 5
Expected: []
Why: neither complete root-to-leaf path sums to 5

Example 3

ready

Input: root = [] targetSum = 0
Expected: []
Why: an empty tree has no root-to-leaf paths

Interview signal

Asked at

AmazonMetaGoogle

The leaf condition carries as much weight as the sum. Every approach must preserve both.

Enumerate every root-to-leaf path

The direct route stores every complete path first. Once enumeration finishes, sum each path and keep the matches.

import sys
 
sys.setrecursionlimit(10_000)
 
 
def path_sum(root: TreeNode | None, target_sum: int) -> list[list[int]]:
    all_paths: list[list[int]] = []
 
    def collect(node: TreeNode | None, path: list[int]) -> None:
        if node is None:
            return
        path.append(node.val)
        if node.left is None and node.right is None:
            all_paths.append(path.copy())
        else:
            collect(node.left, path)
            collect(node.right, path)
        path.pop()
 
    collect(root, [])
    return [path for path in all_paths if sum(path) == target_sum]

Time O(n·h) — copying and summing paths can touch up to h values per visited root-to-leaf sequence. Space O(n·h) — all complete paths stay in memory before the filter runs.

DFS backtracking — keep one working path

Backtracking means you make a choice, explore it, then undo that choice before trying the next branch. Here the choice is appending one node to path. The matching leaf gets a copy because the working list changes as the search continues.

import sys
 
sys.setrecursionlimit(10_000)
 
 
def path_sum(root: TreeNode | None, target_sum: int) -> list[list[int]]:
    answers: list[list[int]] = []
    path: list[int] = []
 
    def dfs(node: TreeNode | None, running_sum: int) -> None:
        if node is None:
            return
 
        path.append(node.val)
        running_sum += node.val
 
        if node.left is None and node.right is None:
            if running_sum == target_sum:
                answers.append(path.copy())
        else:
            dfs(node.left, running_sum)
            dfs(node.right, running_sum)
 
        path.pop()
 
    dfs(root, 0)
    return answers

The final pop() is the hinge. Without it, values from the left branch leak into paths on the right branch.

Time O(n·h) in the worst case because each reported path costs up to h to copy. Space O(h) beyond the returned paths for the working path and call stack.

Python's default recursion limit is lower than an allowed skewed tree can be deep. The code raises that limit before DFS; an explicit stack is the other safe option.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayroot: TreeNode · targetSum: int

Expected

Run: visible + custom · Submit: full suite