Problem statement

Given the root of a binary tree and an integer targetSum, return every root-to-leaf path whose node values add up to targetSum. A leaf is a node with no children, and each path is listed as the node values from the root down to the leaf.

List the paths in the left-to-right order of their leaves. Return an empty list if there are none.

Example 1

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: 5 + 4 + 11 + 2 = 22 and 5 + 8 + 4 + 5 = 22. The path ending at leaf 2 is listed first because that leaf is further left.

Example 2

Input: root = [1,2,3], targetSum = 5
Output: []
Explanation: The two root-to-leaf paths sum to 3 and 4.

Example 3

Input: root = [1,2], targetSum = 1
Output: []
Explanation: The root alone sums to 1, but it is not a leaf — a path must end at a leaf.

Constraints

• 0 <= number of nodes <= 5000
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Hints for Path Sum II

1. Hint 1

   Every candidate path starts at the root and ends at a leaf, so a depth-first walk from the root meets each one exactly once.

2. Hint 2

   Carry the remaining sum down the walk, and keep the current path in one list: add the node on the way in, remove it on the way out.

3. Hint 3

   At a leaf whose remaining sum is exactly 0, record a copy of the path. Visiting the left child before the right one lists the paths in left-to-right order of their leaves.

How to solve Path Sum II

Depth-first search with backtracking: one shared path list grows and shrinks as the walk goes down and back up, and a copy is saved at each leaf where the remaining sum reaches zero.

Approach

1. If the tree is empty, return an empty list.
2. Visit a node with the sum still needed: append its value to the path and subtract it.
3. If the node is a leaf and nothing remains, append a copy of the path to the answer.
4. Visit the left child, then the right child, with the new remaining sum.
5. Remove the node's value from the path before returning.

Why it works

Each root-to-leaf path corresponds to exactly one leaf, and the walk reaches every leaf with the path list holding exactly the nodes from the root to it (values are added on entry and removed on exit), so the checks are exact. Left-before-right recursion reaches the leaves in left-to-right order.

Complexity

• Time — O(n · h): each node is visited once, and copying a matching path costs up to its length h
• Space — O(h) besides the output

Pitfalls

• Store a copy of the path — the shared list keeps changing.
• Values can be negative, so you cannot stop early when the running sum passes the target.
• Only paths that end at a leaf count; an inner node reaching the target is not an answer.

Reference solution

Python

from typing import List, Optional

def pathSum(root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    out = []
    path = []

    def walk(node, remaining):
        path.append(node.val)
        remaining -= node.val
        if node.left is None and node.right is None and remaining == 0:
            out.append(list(path))
        if node.left:
            walk(node.left, remaining)
        if node.right:
            walk(node.right, remaining)
        path.pop()

    if root is not None:
        walk(root, targetSum)
    return out

Java

public static int[][] pathSum(TreeNode root, int targetSum) {
    List<int[]> out = new ArrayList<>();
    if (root != null) sumWalk(root, targetSum, new ArrayList<Integer>(), out);
    return out.toArray(new int[0][]);
}

static void sumWalk(TreeNode node, int remaining, List<Integer> path, List<int[]> out) {
    path.add(node.val);
    remaining -= node.val;
    if (node.left == null && node.right == null && remaining == 0) {
        int[] copy = new int[path.size()];
        for (int i = 0; i < copy.length; i++) copy[i] = path.get(i);
        out.add(copy);
    }
    if (node.left != null) sumWalk(node.left, remaining, path, out);
    if (node.right != null) sumWalk(node.right, remaining, path, out);
    path.remove(path.size() - 1);
}

C++

void sumWalk(TreeNode* node, int remaining, vector<int>& path, vector<vector<int>>& out);

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<vector<int>> out;
    vector<int> path;
    if (root) sumWalk(root, targetSum, path, out);
    return out;
}

void sumWalk(TreeNode* node, int remaining, vector<int>& path, vector<vector<int>>& out) {
    path.push_back(node->val);
    remaining -= node->val;
    if (!node->left && !node->right && remaining == 0) out.push_back(path);
    if (node->left) sumWalk(node->left, remaining, path, out);
    if (node->right) sumWalk(node->right, remaining, path, out);
    path.pop_back();
}

JavaScript

var pathSum = function(root, targetSum) {
    var out = [], path = [];
    function walk(node, remaining) {
        path.push(node.val);
        remaining -= node.val;
        if (node.left === null && node.right === null && remaining === 0) out.push(path.slice());
        if (node.left !== null) walk(node.left, remaining);
        if (node.right !== null) walk(node.right, remaining);
        path.pop();
    }
    if (root !== null) walk(root, targetSum);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Convert Sorted List to Binary Search Tree Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Duplicate Subtree in Binary Tree Medium