1
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.