UserJS - 3 months ago 18x
Java Question

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

Why is "path.remove(path.size()-1)" used in the end?

This code is for finding all root to leaf paths whose sum is equal to given sum.

``````public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
ArrayList<Integer> path = new ArrayList<Integer>();
pathSumRe(root, sum, res, path);
return res;
}
public void pathSumRe(TreeNode root, int sum, List<List<Integer>> res,
ArrayList<Integer> path) {

if (root == null)
return;

if (root.left == null && root.right == null && root.val == sum) {

ArrayList<Integer> tmp = new ArrayList<Integer>(path);
}

pathSumRe(root.left, sum - root.val, res, path);
pathSumRe(root.right, sum - root.val, res, path);
path.remove(path.size() - 1);
}
``````

Removing "path.remove(path.size() - 1);" from the code will give the following output.

Input: [0,1,1], 1

Output: [[0,1],[0,1,1]] ==> This is the wrong output

Expected Output: [[0,1],[0,1]]

The `path.remove(path.size() - 1)` is removing the last added node from the `path` list, as you are reusing the same list for all recursive iterations and are adding the current node with `path.add(root.val);` in each method execution.

The following would be equivalent without reusing the same list (and creating a new one for each execution):

``````public void pathSumRe(TreeNode root, int sum, List<List<Integer>> res,
ArrayList<Integer> path) {
if (root == null) {
return;
}
if (root.left == null && root.right == null && root.val == sum) {
}
pathSumRe(root.left, sum - root.val, res, new ArrayList<Integer>(path));
pathSumRe(root.right, sum - root.val, res, new ArrayList<Integer>(path));
}
``````

This is easier to understand, but creates way more new `ArrayList`s (depending on the tree structure). Regardless of your edit, both versions are working correctly for a TreeNode like this:

``````class TreeNode {
public final int val;
public final TreeNode left;
public final TreeNode right;

public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
``````