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.