Path Sum II

Medium Trees & BST Backtracking Original on LeetCode

Reported atApple

Path Sum II is a medium trees & bst problem solved with the backtracking pattern. The best approach, optimal (dfs backtracking with remaining sum), runs in O(n + total length of the answer paths) time and O(h) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (collect every path, then filter) up.

Problem

Given the root of a binary tree and an integer targetSum, return every root-to-leaf path whose node values add up to targetSum. Each path is a list of the node values from the root down to the leaf.

A leaf is a node with no children. The paths may be returned in any order.

Examples

Example 1

Input
root = [6, 2, 3, 4, 4, 1, 3], targetSum = 12
Output
[[6, 2, 4], [6, 2, 4], [6, 3, 3]]
Why
6 + 2 + 4 = 12 twice (two different leaves with value 4) and 6 + 3 + 3 = 12; 6 + 3 + 1 = 10 does not count.

Example 2

Input
root = [1, -2, 3, null, 5], targetSum = 4
Output
[[1, -2, 5], [1, 3]]
Why
Negative values are allowed; paths can have different lengths.

Example 3

Input
root = [], targetSum = 0
Output
[]
Why
An empty tree has no root-to-leaf paths, even for a target of 0.

Constraints

  • The number of nodes is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (collect every path, then filter)O(n · h)O(n · h)
Optimal (DFS backtracking with remaining sum)O(n + total length of the answer paths)O(h)

1Brute force (collect every path, then filter)

TimeO(n · h)Each of the n nodes copies a path of length up to h (the height); summing the stored paths costs the same.
SpaceO(n · h)Every leaf's full path is stored, and every call holds its own copy.

Generate every root-to-leaf path as its own fresh list (copying the path at each step), then keep the ones whose values add up to the target. Simple, but it copies the path at every node.

  1. DFS from the root with a list path; at each node make a new list path + [node.val].
  2. At a leaf, store that list in allPaths.
  3. After the DFS, return the lists in allPaths whose sum equals targetSum.
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> allPaths = new ArrayList<>();
        collect(root, new ArrayList<>(), allPaths);
        List<List<Integer>> res = new ArrayList<>();
        for (List<Integer> p : allPaths) {
            int sum = 0;
            for (int v : p) sum += v;
            if (sum == targetSum) res.add(p);
        }
        return res;
    }

    private void collect(TreeNode node, List<Integer> path, List<List<Integer>> allPaths) {
        if (node == null) return;
        List<Integer> next = new ArrayList<>(path);
        next.add(node.val);
        if (node.left == null && node.right == null) {
            allPaths.add(next);
            return;
        }
        collect(node.left, next, allPaths);
        collect(node.right, next, allPaths);
    }
}

2Optimal (DFS backtracking with remaining sum)

TimeO(n + total length of the answer paths)Each node is entered and left once with O(1) work; copying happens only for the matching paths (in the worst case O(n · h) total).
SpaceO(h)The shared path and the recursion stack are both as deep as the tree height h (not counting the output).

Walk the tree once with a single shared path list and the sum still needed. Push the node's value on entry and pop it on exit, so path always holds the current root-to-node route. Only when a leaf brings the remaining sum to exactly 0 is the path copied into the answer.

  1. dfs(node, remain): if node is null, return.
  2. Append node.val to path and set remain -= node.val.
  3. If node is a leaf and remain == 0, add a copy of path to the answer.
  4. Otherwise recurse into the left and right children with remain.
  5. Remove the last element of path before returning (backtrack).
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), res);
        return res;
    }

    private void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> res) {
        if (node == null) return;
        path.add(node.val);
        remain -= node.val;
        if (node.left == null && node.right == null) {
            if (remain == 0) res.add(new ArrayList<>(path));
        } else {
            dfs(node.left, remain, path, res);
            dfs(node.right, remain, path, res);
        }
        path.remove(path.size() - 1);
    }
}

Edge cases to test

  • Empty tree
  • A single node equal (or not equal) to the target
  • Negative values, so a partial sum can pass the target and come back
  • A node with one child is not a leaf: the path must continue to a real leaf
  • Several different leaves producing identical value lists

Hints

Hint 1

A path only counts if it ends at a leaf, a node with no children at all.

Hint 2

Walk the tree with DFS, carrying the remaining sum targetSum - (values so far).

Hint 3

Use one shared path list: add the node on the way down and remove it on the way back up (backtracking). Copy the path only when a leaf matches.

FAQ

What is the best time complexity for Path Sum II?

Optimal (DFS backtracking with remaining sum) runs in O(n + total length of the answer paths) time and O(h) extra space. Each node is entered and left once with O(1) work; copying happens only for the matching paths (in the worst case O(n · h) total).

Which pattern does Path Sum II use?

It is a trees & bst problem that uses the backtracking pattern. Other problems with the same pattern: Root to Leaf Paths, Path Sum III.

Is there a brute force solution for Path Sum II?

Yes. Brute force (collect every path, then filter) takes O(n · h) time and O(n · h) space. Generate every root-to-leaf path as its own fresh list (copying the path at each step), then keep the ones whose values add up to the target.

Which edge cases should I test for Path Sum II?

Empty tree; A single node equal (or not equal) to the target; Negative values, so a partial sum can pass the target and come back; A node with one child is not a leaf: the path must continue to a real leaf; Several different leaves producing identical value lists.