Path Sum II

medium tree dfs backtracking

Problem

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values equals targetSum. A leaf is a node with no children.

Inputroot = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

Output[[5,4,11,2],[5,8,4,5]]

Two root-to-leaf paths sum to 22.

tree (level-order, "null" for empty)

targetSum

def path_sum(root, target):
    result, path = [], []
    def dfs(node, remaining):
        if not node: return
        path.append(node.val)
        remaining -= node.val
        if not node.left and not node.right and remaining == 0:
            result.append(path[:])
        dfs(node.left, remaining)
        dfs(node.right, remaining)
        path.pop()
    dfs(root, target)
    return result

function pathSum(root, target) {
  const result = [], path = [];
  function dfs(node, remaining) {
    if (!node) return;
    path.push(node.val);
    remaining -= node.val;
    if (!node.left && !node.right && remaining === 0) result.push(path.slice());
    dfs(node.left, remaining);
    dfs(node.right, remaining);
    path.pop();
  }
  dfs(root, target);
  return result;
}

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, target, new ArrayList<>(), result);
        return result;
    }
    void dfs(TreeNode n, int remaining, List<Integer> path, List<List<Integer>> out) {
        if (n == null) return;
        path.add(n.val);
        remaining -= n.val;
        if (n.left == null && n.right == null && remaining == 0) out.add(new ArrayList<>(path));
        dfs(n.left, remaining, path, out);
        dfs(n.right, remaining, path, out);
        path.remove(path.size() - 1);
    }
}

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        vector<vector<int>> result;
        vector<int> path;
        dfs(root, target, path, result);
        return result;
    }
    void dfs(TreeNode* n, int rem, vector<int>& path, vector<vector<int>>& out) {
        if (!n) return;
        path.push_back(n->val);
        rem -= n->val;
        if (!n->left && !n->right && rem == 0) out.push_back(path);
        dfs(n->left, rem, path, out);
        dfs(n->right, rem, path, out);
        path.pop_back();
    }
};

Explanation

We need every root-to-leaf path whose values add up to the target. The natural tool is DFS with backtracking: walk down building a path, and whenever we hit a leaf that finishes the target, save a copy of that path.

We carry two things as we recurse: the current path (a growing list of values) and remaining, the target minus everything taken so far. At each node we push its value and subtract it from remaining.

The win condition is precise: a node is a leaf (no left or right child) and remaining == 0. When both hold we append a snapshot path[:] to the results — a copy, since the live path keeps changing.

The backtracking line path.pop() is essential. After exploring both children of a node, we remove that node from the path so a sibling branch starts with a clean trail. This is how one list serves every path.

Example: target 22. The path 5 → 4 → 11 → 2 sums exactly to 22 and ends at a leaf, so it is recorded; likewise 5 → 8 → 4 → 5. Other branches either overshoot or end short and are skipped.

Time: O(n²) worst case (copying paths) Space: O(h) recursion + output