# Path Sum II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/path-sum-ii)
Canonical: https://scaleengineer.com/dsa/problems/path-sum-ii
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [Oracle](https://scaleengineer.com/companies/oracle), [TikTok](https://scaleengineer.com/companies/tiktok), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## 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 in the path equals_ `targetSum`_. Each path should be returned as a list of the node **values**, not node references_.

A **root-to-leaf** path is a path starting from the root and ending at any leaf node. A **leaf** is a node with no children.

**Example 1:**

![](https://assets.glich.co/dsa/path-sum-ii/image0.jpg) 

**Input:** root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
**Output:** [[5,4,11,2],[5,8,4,5]]
**Explanation:** There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

**Example 2:**

![](https://assets.glich.co/dsa/path-sum-ii/image1.jpg) 

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

**Example 3:**

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

**Constraints:**

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

# Approaches
## DFS with Path Copying
This approach uses a standard Depth-First Search (DFS) traversal. The core idea is to explore each possible root-to-leaf path. For each node visited, we create a new list that represents the path from the root to the current node. This is done by copying the path of the parent node and appending the current node. This new path is then passed down to its children in subsequent recursive calls. While conceptually simple, this method is inefficient because of the repeated creation of list copies at every step of the recursion.
**Time:** O(N*H) · **Space:** O(N*H)
**Pros:** The logic is straightforward and easy to understand.; The state for each recursive call (the path) is completely independent, which can prevent certain bugs related to shared state.
**Cons:** Highly inefficient in terms of both time and space.; Creating a new copy of the path list at every node in the tree leads to significant overhead, especially for deep or large trees.
### Explanation
The algorithm explores the tree from the root downwards. It maintains the sum of the nodes along the path it is currently exploring. A helper function is used to carry the state of the traversal, which includes the current node, the sum still needed to reach the target (`remainingSum`), and the list of nodes in the current path.

At each node, we create a brand new list by copying the path that led to the parent and add the current node's value. We then update the `remainingSum`. If the current node is a leaf and the `remainingSum` is zero, we have found a valid path and add our new path list to the list of results. We then continue this process recursively for the left and right children.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        findPaths(root, targetSum, new ArrayList<>(), result);
        return result;
    }

    private void findPaths(TreeNode node, int remainingSum, List<Integer> currentPath, List<List<Integer>> result) {
        if (node == null) {
            return;
        }

        // Create a new path list for the path including the current node
        List<Integer> newPath = new ArrayList<>(currentPath);
        newPath.add(node.val);

        int newRemainingSum = remainingSum - node.val;

        // Check if it's a leaf node and the sum matches
        if (node.left == null && node.right == null && newRemainingSum == 0) {
            result.add(newPath);
            return;
        }

        // Recurse for left and right children, passing the new path
        findPaths(node.left, newRemainingSum, newPath, result);
        findPaths(node.right, newRemainingSum, newPath, result);
    }
}
```
### Algorithm
1. Define a recursive helper function, for example, `findPaths(node, remainingSum, currentPath, result)`.
2. The base case for the recursion is when the `node` is `null`. In this case, simply return.
3. Inside the function, create a new list (`newPath`) by copying the `currentPath` and add the current node's value to it.
4. Subtract the current node's value from `remainingSum`.
5. Check if the current node is a leaf (both `left` and `right` children are `null`) and if the `remainingSum` is now zero.
6. If both conditions are true, it means we've found a valid path. Add the `newPath` to the final `result` list.
7. Recursively call the `findPaths` function for the left and right children, passing the updated `remainingSum` and the `newPath`.
8. The main function will initialize an empty list for the results and call the helper function with the root node, the initial `targetSum`, and an empty path.

## DFS with Backtracking
This approach also uses Depth-First Search (DFS) but optimizes the process by using backtracking. Instead of creating a new path list for every recursive call, we use a single list to keep track of the current path. When we move down the tree to a child, we add its value to the list. After the recursive call for that child's subtree returns, we remove the value from the list. This action of removing the element is called 'backtracking'. It ensures that when we explore a sibling node, the path is correctly set to the state of the parent. This avoids the expensive operation of copying the path at every node, making it much more efficient in both time and space.
**Time:** O(N) for traversing all nodes. The total time is O(N + K*H) where K is the number of valid paths and H is the tree height, to account for copying valid paths to the result. · **Space:** O(H) or O(N) in the worst case (skewed tree), where H is the height of the tree. This is for the recursion stack and the path list, excluding the output.
**Pros:** Very efficient in terms of time and space.; Avoids the overhead of creating new lists at each recursive step.; It's the standard and optimal solution for this type of path-finding problem in trees.
**Cons:** Backtracking can be slightly more complex to implement correctly compared to passing copies.; Requires careful state management of the shared path list to avoid bugs.
### Explanation
The algorithm traverses the tree using a recursive DFS function. We maintain a single list, `path`, which stores the nodes of the path currently being explored. When the DFS function is called on a node, we add that node's value to `path`. We then check if it's a leaf node and if the path sum equals the `targetSum`. If it does, we create a copy of the current `path` and add it to our list of results. We then proceed to make recursive calls for the left and right children. The crucial step happens after these recursive calls return: we remove the current node's value from `path`. This backtracking step ensures that the `path` list is restored to its state before visiting the current node, making it ready for the exploration of other branches of the tree.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> result;
    List<Integer> path;

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

    private void findPaths(TreeNode node, int remainingSum) {
        if (node == null) {
            return;
        }

        // Add current node to the path
        path.add(node.val);
        remainingSum -= node.val;

        // Check if it's a leaf and the sum is met
        if (node.left == null && node.right == null && remainingSum == 0) {
            result.add(new ArrayList<>(path));
        }

        // Recurse on children
        findPaths(node.left, remainingSum);
        findPaths(node.right, remainingSum);

        // Backtrack: remove the current node from the path
        path.remove(path.size() - 1);
    }
}
```
### Algorithm
1. Define a recursive helper function, e.g., `findPaths(node, remainingSum)` that uses shared lists for the result and the current path (e.g., as member variables).
2. The base case is when `node` is `null`; simply return.
3. Add the current node's value to the `currentPath` list.
4. Subtract the node's value from `remainingSum`.
5. Check if the current node is a leaf (`node.left == null && node.right == null`) and if `remainingSum` is zero.
6. If so, a valid path is found. Add a *copy* of the `currentPath` to the `result` list. It's crucial to add a copy, as the `currentPath` list will be modified later during backtracking.
7. Recursively call the helper function for the left and right children with the updated `remainingSum`.
8. After the recursive calls for the children return, remove the current node's value from the end of `currentPath`. This is the **backtracking** step. It cleans up the path, effectively moving up one level in the tree, allowing other branches to be explored correctly.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private List < List < Integer >> ans = new ArrayList <>(); private List < Integer > t = new ArrayList <>(); public List < List < Integer >> pathSum ( TreeNode root , int targetSum ) { dfs ( root , targetSum ); return ans ; } private void dfs ( TreeNode root , int s ) { if ( root == null ) { return ; } s -= root . val ; t . add ( root . val ); if ( root . left == null && root . right == null && s == 0 ) { ans . add ( new ArrayList <>( t )); } dfs ( root . left , s ); dfs ( root . right , s ); t . remove ( t . size () - 1 ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {number[][]} */ var pathSum =
  function (root, targetSum) {
    const ans = [];
    const t = [];
    function dfs(root, s) {
      if (!root) return;
      s -= root.val;
      t.push(root.val);
      if (!root.left && !root.right && s == 0) ans.push([...t]);
      dfs(root.left, s);
      dfs(root.right, s);
      t.pop();
    }
    dfs(root, targetSum);
    return ans;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < vector < int >> pathSum ( TreeNode * root , int targetSum ) { vector < vector < int >> ans ; vector < int > t ; function < void ( TreeNode * , int ) > dfs = [ & ]( TreeNode * root , int s ) { if ( ! root ) return ; s -= root -> val ; t . emplace_back ( root -> val ); if ( ! root -> left && ! root -> right && s == 0 ) ans . emplace_back ( t ); dfs ( root -> left , s ); dfs ( root -> right , s ); t . pop_back (); }; dfs ( root , targetSum ); return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def pathSum ( self , root : Optional [ TreeNode ], targetSum : int ) -> List [ List [ int ]]: def dfs ( root , s ): if root is None : return s += root . val t . append ( root . val ) if root . left is None and root . right is None and s == targetSum : ans . append ( t [:]) dfs ( root . left , s ) dfs ( root . right , s ) t . pop () ans = [] t = [] dfs ( root , 0 ) return ans
```