> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/tree-traversal/binary-tree-path-sum.md).

# Binary Tree Path Sum

## Question ([LI.376](http://www.lintcode.com/en/problem/binary-tree-path-sum/#))

> Given the root of a binary tree, from all paths from root -> leaf that sum to the target value.

## Example

```
I: {1,2,4,2,3}, 5
O: [[1,2,2],[1,4]]
```

Can the values be negative? It doesn't matter we need to go down all the way anyway

## Approach

~~D\&C will be long to implement because the CEO has the final say on the report but we need to make that a special case. Instead, we can just traverse from the root.~~

This question is the same as Binary Tree Paths. D\&C has a simpler implementation.

## D\&C

```java
public List<List<Integer>> binaryTreePathSum(TreeNode root, int targetSum) {
    List<List<Integer>> paths = new ArrayList<>();
    // base
    if (root == null) {
        return paths;
    }
    if (root.left == null && root.right == null) {
        if (root.val == targetSum) {
            List<Integer> path = new ArrayList<>();
            path.add(root.val);
            paths.add(path);
        }
        return paths;
    }
    // divide and conquer
    List<List<Integer>> leftPaths = binaryTreePathSum(root.left, targetSum - root.val);
    List<List<Integer>> rightPaths = binaryTreePathSum(root.right, targetSum - root.val);
    // merge
    for (List<Integer> path : leftPaths) {
        path.add(0, root.val);
        paths.add(path);
    }
    for (List<Integer> path : rightPaths) {
        path.add(0, root.val);
        paths.add(path);
    } 
    return paths;
}
```

## Traversal

```java
public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
    List<List<Integer>> paths = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    traverseHelper(root, target, paths, path);
    return paths;
}

// 2 cases leaf or incomplete branch
// we want to stop at leaf and skip incomplete branch
private void traverseHelper(TreeNode root, 
                            int target, 
                            List<List<Integer>> paths, 
                            List<Integer> path) {
    // incomplete branch
    if (root == null) {
        return;
    }
    // leaf (the path right now is root->leaf)
    if (root.left == null && root.right == null) {
        if (target - root.val == 0) {
            path.add(root.val);
            paths.add(new ArrayList<>(path));
            path.remove(path.size() - 1);
        }
        return;
    }
    // traverse
    path.add(root.val);
    traverseHelper(root.left, target - root.val, paths, path);
    path.remove(path.size() - 1);

    path.add(root.val);
    traverseHelper(root.right, target - root.val, paths, path);
    path.remove(path.size() - 1);        
}
```