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

Question

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<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> curList = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> 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<Integer>(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;
}

Answer 1

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<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> curList = new ArrayList<Integer>();
    pathSum(root, sum, curList, res);
    return res;
}


private void pathSum(TreeNode root, int sum, 
            ArrayList<Integer> curList, ArrayList<ArrayList<Integer>> 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<List<Integer>> and not ArrayList<ArrayList<Integer>>
• 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....

Answer 2

I'm dissatisfied with

curList.remove(new Integer(root.val));

You should treat curList like a stack: push an element for each step during the descent, and pop an element for each level you backtrack. I suggest using a LinkedList<Integer> for curList as a Deque, giving you O(1) push() and pop() operations.

In contrast, curList.remove(new Integer(root.val)) takes O(d) time, where d is the depth. More importantly, remove() removes the first occurrence of the number from curList, not the last. Therefore, if the tree has duplicate values along a root-to-leaf-path, it would report the nodes in a wrong order.

Answer 3

• You said top-tier, so go read Google's style guide and follow it: spaces around operators, a space after if and friends and before open curly braces, don't name collections after the specific type (curPath vs. curList).

• Before adding the current node's value to curList and checking for children, make sure the sum hasn't passed the desired total. Exit early if it has to avoid processing the subtree of impossible paths. This assumes negative values are not allowed.

• Recursive algorithm: +1. "Global" state: -10. @rolfl covered this well.

• I would prefer to see you use a true stack rather than treating a list as one. Under the hood it's probably the same, but there is a semantic difference that's lost by using a list.

• Put the left/right child handling in an else block to bypass it when a leaf that doesn't add up to the desired sum is found. Do this to clarify the logic rather than for the trivial performance boost.

Answer 4

Every thing is correct, except for the removal of an integer from the path root to leaves. Removal of duplicate elements along path was not handled properly as ArrayList.remove() removes elements from starting. You just need to do the following add Collections.reverse(List) and then remove and then reverse again Collections.reverse(List). This assures that the last added element is removed first.

Answer 5

There are a few things that could be better:

• You should make it generic.
• Personally, I think you should use an array to store the children, even if there are only two; it can make it a lot more DRY.