Find the sum along root-to-leaf paths of a tree

Most of you already know me, please be brutal, and treat this code as if it was written at a top tech interview company.

Question:


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


For example: Given the below binary tree and sum = 22,

5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Time taken: 26 minutes (all 110 test cases passed)

Worst case: \$O(n^2)\$?

Since when I add to resList, it copies all the elements again which can take \$O(n)\$ and I traverse \$O(n)\$ nodes.

Space complexity: \$O(n)\$

My code:

ArrayList> res = new ArrayList>();
ArrayList curList = new ArrayList();
public ArrayList> pathSum(TreeNode root, int sum) {
    if(root==null){
        return res;
    }
    curList.add(root.val);
    if(root.left==null && root.right==null){
        if(sum - root.val==0){
            res.add(new ArrayList(curList));
        }
    }
    if(root.left!=null){
        pathSum(root.left, sum-root.val);
    }
    if(root.right!=null){
        pathSum(root.right, sum-root.val);
    }
    curList.remove(new Integer(root.val));
    return res;
}

You are treating res and curList as if they are Globals, and, since they are globals, there is no reason to return ret in the function at all.

As a result of this, your code is not re-entrant (you can only have one method calling your pathSum at any one point in time).

The right solution to this is to pass the curList and ret values as parameters to the method, convert it to private, and create a new public method which creates the instances as you need them.....

public ArrayList> pathSum(TreeNode root, int sum) {
    ArrayList> res = new ArrayList>();
    ArrayList curList = new ArrayList();
    pathSum(root, sum, curList, res);
    return res;
}

private void pathSum(TreeNode root, int sum, 
            ArrayList curList, ArrayList> res) {
    ....
    ** change the methods called as part of the recursion too**
    ....
}

That is the big structural change, but I would recommend more:

• methods should not return specific List implementation types unless those types have special features you need. your method should return List> and not ArrayList>

• convert curList to an array of int[], and the return valye of the system to List

• you do the calculation sum-root.val in multiple places. Firstly, it should be spaced properly: sum - root.val, and secondly, you should save it as a variable once, and re-use that variable in the places where it currently is a function

About the complexity

you ask if worst case is \$O(n^2)\$ ... no, it is not.

Worst case is \$O(n \log(n))\$. This is my reasoning:

• the depth of a binary tree is about \$\log(n)\$.

• The deepest a binary tree can be is depth n, but, in that case there is only one possible solution, so the complexity will be two \$O(n)\$ operations, one to scan the single deep branch, and another to copy the array.

• the worst case is actually a fully-balanced tree where every leaf node matches the intended sum, in which case the number of solutions is proportional to \$O(n)\$, but the actual copy to the array will be of \$O(log(n))\$ elements

So, My assessment is \$O(n \log(n))\$

Feel free to debate this... I am not 100% certain....

StackExchange Code Review Q#46765, answer score: 5