5.12 Path Sum II

5.12.1 Problem Metadata

5.12.2 Description

Find all root-to-leaf paths where the sum of node values equals a target.

5.12.3 Solution - Backtracking

5.12.3.1 Walkthrough

This problem uses the 2-dimensional traversal mental model of backtracking (see Pattern 1: Choose-Explore-Unchoose):

  • Outer dimension (recursion parameter): node / depth in the tree - controls how deep we’ve traversed
  • Inner dimension (implicit traversal): At each node, we have up to 2 choices (left child and right child)

The backtracking explores the tree as a conceptual decision space where each level represents a depth in the tree, and at each level we “choose” to include the current node’s value in the path.

Key mechanism: Traverse the tree, maintaining the current path list and remaining sum. When a leaf reaches zero remaining sum, append a copy of the path to the answer. Backtrack after exploring each branch to try other paths.

5.12.3.2 Analysis

  • Time Complexity: O(n * h)
  • Space Complexity: O(h)

5.12.3.3 Code - Java

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(root, targetSum, new ArrayList<>(), result);
    return result;
}

private void backtrack(TreeNode node, int remain, List<Integer> path, List<List<Integer>> result) {
    if (node == null) {
        return;
    }

    path.add(node.val);
    remain -= node.val;

    if (node.left == null && node.right == null && remain == 0) {
        result.add(new ArrayList<>(path));
    } else {
        backtrack(node.left, remain, path, result);
        backtrack(node.right, remain, path, result);
    }

    path.remove(path.size() - 1);
}