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. Each path should be returned as a list of node values.

Examples

Example 1:

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

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 1
Output: []

Constraints

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

Thinking Process

This is LC 112 Path Sum extended to collect all valid paths instead of just returning true/false.

From LC 112 to LC 113

LC 112 LC 113
Return bool Return all matching paths
Can short-circuit on first match Must explore the entire tree
No path tracking needed Maintain a running path + backtrack

Backtracking Pattern

  1. Push the current node’s value onto the path
  2. At a leaf, if remaining sum is 0, copy the path to results
  3. Recurse on children
  4. Pop the current node (backtrack)

The push/pop ensures the path is always correct for the current branch.

Approach: DFS + Backtracking – $O(n^2)$

class Solution {
    public int[][] pathSum(TreeNode root, int targetSum) {
        int[][] rtn;
        int[]pathNodes;
        traversePaths(root, targetSum, pathNodes, rtn);
        return rtn;
    }
    void traversePaths(TreeNode node, int remainingSum,
                       int[] pathNodes, int[][]& pathsList) {
        if (!node) return;

        remainingSum -= node.val;
        pathNodes.add(node.val);

        if (!node.left && !node.right && remainingSum == 0) {
            pathsList.add(pathNodes);
        } else {
            traversePaths(node.right, remainingSum, pathNodes, pathsList);
            traversePaths(node.left, remainingSum, pathNodes, pathsList);
        }

        pathNodes.removeLast();
    }
}

Time: $O(n^2)$ worst case – visit $n$ nodes, each valid path copy is $O(n)$ Space: $O(h)$ recursion + path storage (excluding output)

Common Mistakes

  • Forgetting pathNodes.pop_back() after recursion (corrupts the path for sibling branches)
  • Copying the path at every node instead of only at leaves
  • Not handling the empty tree case (null root returns [], not [[]])

Key Takeaways

  • This is the standard backtracking-on-tree template: push → check/recurse → pop
  • The transition from LC 112 → 113 is a common interview escalation: “now collect all answers”
  • Same pattern applies to LC 257 (all root-to-leaf paths as strings)

Template Reference