# Find all k-sum paths in a binary tree

Posted on

Problem

Description:

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.

Leetcode

Code:

``````class Solution {
private List<List<Integer>> paths = new ArrayList<>();

public List<List<Integer>> pathSum(TreeNode root, int sum) {
traverse(root, sum, new ArrayList<Integer>());
return paths;
}

private void traverse(TreeNode root, int sum, ArrayList<Integer> path) {
if (root != null) {

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

traverse(root.left,  sum - root.val, path);
traverse(root.right, sum - root.val, path);

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

Solution

It’s a fine solution. I have a few minor comments.

• It’s easy to overlook that `pathSum` doesn’t clear the content of `paths`, which will affect the returned value from subsequent calls, which is likely to be unexpected by callers. In this online puzzle it doesn’t seem to matter, but I think it’s better to avoid any possible confusion.

• The `clone` with the cast is ugly. The `.clone()` method except on arrays is a bit controversial, with questionable benefits if any. I suggest to avoid it. You can replace it with a nice clean `paths.add(new ArrayList<>(path))`

• The signature of `traverse` would be better to use `List` instead of `ArrayList`.

• I would use an early return in `traverse`, to have less indented code.