Faangprep Logo
Log inStart free
Browse curriculum

Path Sum II

Find all root-to-leaf paths where each path's sum equals the targetSum.

MediumSolve on LeetCode

Examples

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

Two paths sum to 22.

Problem Understanding

Unlike Path Sum I, we need to return every root-to-leaf path whose values add up to targetSum, not just whether one exists.

Since we need the paths themselves, we keep one path list that always holds the nodes from the root down to the current call. When we reach a leaf that completes the sum, we add a copy of path to result.

Algorithm Strategy (Backtracking)

We use DFS with backtracking.

  1. State: one shared path list, and remaining, what is still needed.
  2. Action: entering a node, append node.val to path.
  3. Check: at a leaf whose value is exactly remaining, save a copy of path.
  4. Recurse: otherwise call the left and right children with remaining - node.val.
  5. Backtrack: pop node.val off path before returning, so the parent’s other branch starts from the right path.

Interactive Visualization

The outlined nodes are path itself: a node joins when its call starts and leaves just before its call returns. Each visited node shows what was still needed below it, and a leaf whose path is saved turns green.

Dry Run: [1, 2, 3], Target = 4

Tree: [1, 2, 3], target = 4

Step Call path Action
1 dfs(1, 4) [1] Not a leaf: go left needing 3
2 dfs(2, 3) [1, 2] A leaf, but 3 ≠ 2: call both empty children
3 back in dfs(2) [1] Pop 2
4 dfs(3, 3) [1, 3] A leaf and 3 = 3: save [1, 3]
5 back in dfs(3) [1] Pop 3
6 back in dfs(1) [] Pop 1 — return [[1, 3]]

Edge Cases & Common Mistakes

  • Save a copy: path is one shared list. Adding it to result directly would leave every entry pointing at the same list, which ends up empty. Add list(path), new ArrayList<>(path) or [...path].
  • Pop in every case: the pop must run after both branches — and also after a saved leaf — or the path keeps nodes that are no longer being visited.
  • Negative values: the sum can pass the target and come back, so never stop early just because the running sum is too large.

Solution

Backtracking approach.

Path Sum II Code
1var pathSum = function(root, targetSum) {
2    const result = [];
3    const path = [];
4

5    function dfs(node, remaining) {
6        if (!node) return;
7        path.push(node.val);
8        if (!node.left && !node.right && remaining === node.val) {
9            result.push([...path]);
10        } else {
11            dfs(node.left, remaining - node.val);
12            dfs(node.right, remaining - node.val);
13        }
14        path.pop();
15    }
16

17    dfs(root, targetSum);
18    return result;
19};
Previous

Lowest Common Ancestor of a Binary Tree

Next

Longest Univalue Path

The approach, step by step

  1. Append the node

    Add the node’s value to the path.

  2. Save or recurse

    At a leaf whose value is exactly what remains, save a copy; otherwise recurse into both children.

  3. Backtrack

    Pop the node from the path before returning.

Frequently asked questions

How do you find all root-to-leaf paths with a given sum?

Walk the tree with DFS while keeping one path list. Append each node on the way down, save a copy of the path at a leaf that completes the sum, and pop the node before returning.

Why must the path be copied when saved?

The path list is shared and keeps changing as the search continues. Saving it without copying would leave every saved entry pointing at the same list.

What is the complexity?

Visiting the nodes is O(n), but copying a path of up to n nodes at up to n leaves makes the worst case O(n²). The path and recursion use O(n) space.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description