Sum of all Paths in Binary Tree

Question

Problem

For the given binary tree return the list which has sum of every paths in a tree. i.e Every path from root to leaf.

I've written following solution.

void check()
 {
 List<Integer> out = new ArrayList<>();
 leafsum(root, 0, out);
 System.out.println(out);
 }
 void leafsum(TreeNode root, int curr , List<Integer> sum)
 {
 if(root != null)
 {
 leafsum(root.left, curr+root.data, sum);
 if(root.left == null && root.right == null ) sum.add(curr+root.data);
 leafsum(root.right, curr+root.data, sum);
 }
 }

Inorder traversal of Tree

2 4 3 5 1 9 2 5 15

root = new TreeNode(5);
root.left = new TreeNode(4);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(3);
root.right = new TreeNode(9);
root.right.right = new TreeNode(5);
root.right.left = new TreeNode(1);
root.right.right.left = new TreeNode(2);
root.right.right.right = new TreeNode(15);

Output

[11, 12, 15, 21, 34]

I would like review about improvements and suggestions.

Answer 1

Formatting

The formatting could be nicer and doesn't follow Java conventions.

• The indention isn't correct (maybe a copy and paste error).
• Opening braces belong on the same line as the method header/statement.
• There are random superfluous spaces (after int curr and root.right == null) and missing spaces around the + operator in curr+root.data
• There should be a space between keywords and opening brackets (if (...).
• Braces should always be used around a conditional block, even if it only contains a single statement.
• There shouldn't be more than a single blank line at a time and there shouldn't any at all inside leafsum in my opinion.

Names

The parameter names could be better:

• root should be node.
• There is no need to abbreviate curr. It should be current or maybe even currentSum.
• The list should have a plural name: sums.

The method itself should also have a plural name such as leafSums.

Early return

In order to minimize indention depth return early out of leafsum instead of putting the complete method body inside the if block:

void leafsum(TreeNode root, int curr, List<Integer> sum) {
 if (root == null) {
 return;
 }
 // method body here.
}

DRY

You are repeating the sum curr + root.data three times.

Handling results

I'm not a big fan creating, carrying around and mutating a list for the results, however your way is probably the least convoluted way with Java's standard collection library. Personally I'd do something like:

static List<Integer> leafSums(TreeNode node, int currentSum) {
 if (node == null) {
 return Collections.emptyList();
 }
 int newSum = currentSum + node.data;
 List<Integer> leftSums = leafSums(node.left, newSum);
 List<Integer> rightSums = leafSums(node.right, newSum);
 List<Integer> sums = new ArrayList<>(leftSums);
 if (node.left == null && node.right == null) {
 sums.add(newSum);
 }
 sums.addAll(rightSums);
 return sums;
}

except I'd look for alternative to ArrayList that allows more efficient list concatenation with a nicer API.