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

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

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.

Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

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

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> rtn;
        vector<int> pathNodes;
        traversePaths(root, targetSum, pathNodes, rtn);
        return rtn;
    }

private:
    void traversePaths(TreeNode* node, int remainingSum,
                       vector<int>& pathNodes, vector<vector<int>>& pathsList) {
        if (!node) return;

        remainingSum -= node->val;
        pathNodes.push_back(node->val);

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

        pathNodes.pop_back();
    }
};

Solution Explanation

Approach: Recursive DFS (this problem)

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

How the code works:

  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)

Walkthrough — input root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22, expected output [[5,4,11,2],[5,8,4,5]]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected 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)

References

Template Reference