> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/trees/path-sum-ii.md).

# Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

**Note:** A leaf is a node with no children.

**Example:**

Given the below binary tree and`sum = 22`,

```
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
```

Return:

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

## Analysis

Similar to Path Sum I, using DFS to find the path with a targeted sum, yet it requires additional space to store the intermediate results, thus creating helper function with temporal results argument.

One tricky part is to add root.val to the temporal results first and check if it matches targeted sum (passed in), if so remove it from temporal results, because the same temporal list will be used in a different branch as well

## Solution

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> paths = new LinkedList<List<Integer>>();
        List<Integer> currentPath = new LinkedList<Integer>();
        if (root == null) return paths;
        pathSumHelper(root, sum, currentPath, paths);
        return paths;
    }
    void pathSumHelper(TreeNode root, int sum, List<Integer> currentPath, List<List<Integer>> paths) {
        if (root == null) return;
        currentPath.add(new Integer(root.val));
        if (root.val == sum && root.left == null && root.right == null) {
            paths.add(new LinkedList(currentPath));
            // remember to remove the last element for upper level recursive call
            currentPath.remove(currentPath.size() - 1); 
            return;
        } else {
            pathSumHelper(root.left, sum - root.val, currentPath, paths);
            pathSumHelper(root.right, sum - root.val, currentPath, paths);
        }
        // remember to remove the last element for upper level recursive call
        currentPath.remove(currentPath.size() - 1); 
    }
}
```

Simplify Back-tracking

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<List<Integer>> allValidPaths;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        allValidPaths = new ArrayList<>();
        traverse(root, sum, 0, new ArrayList<>());
        return allValidPaths;
    }

    private void traverse(TreeNode node, int sum, int currSum, List<Integer> sumPath) {
        if(node == null) return;

        currSum += node.val;
        sumPath.add(node.val);
        if(node.left == null && node.right == null && currSum == sum) {
            allValidPaths.add(new ArrayList<>(sumPath));
        }
        else {
            traverse(node.left, sum, currSum, sumPath);
            traverse(node.right, sum, currSum, sumPath);
        }

        sumPath.remove(sumPath.size()-1);
    } 
}
```

Simplify Helper Function

```java
class Solution {
    private List<List<Integer>> allValidPaths;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        allValidPaths = new ArrayList<>();
        traverse(root, sum, new ArrayList<>());
        return allValidPaths;
    }

    private void traverse(TreeNode node, int sum, List<Integer> sumPath) {
        if(node == null) return;

        sumPath.add(node.val);
        if(node.left == null && node.right == null && node.val == sum) {
            allValidPaths.add(new ArrayList<>(sumPath));
        }
        else {
            traverse(node.left, sum - node.val, sumPath);
            traverse(node.right, sum - node.val, sumPath);
        }

        sumPath.remove(sumPath.size()-1);
    } 
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/trees/path-sum-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.