7
\$\begingroup\$

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; }
\$\endgroup\$

5 Answers 5

Reset to default
5
\$\begingroup\$

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....

\$\endgroup\$
9
  • \$\begingroup\$ Using int[] will necessitate copying it to add an element every time you descend into a child. \$\endgroup\$ Commented Apr 10, 2014 at 1:20
  • \$\begingroup\$ @DavidHarkness - creating an oversize array with a size to use as a stack, and then only making a copy when I have a sum-match is the way I would do it. This is faster than copying the current-array anyway. \$\endgroup\$ Commented Apr 10, 2014 at 1:22
  • \$\begingroup\$ I must have misunderstood your item about using an int[] because your comment describes what the current code does. It doesn't overly size the list, but the default is 10 IIRC. Using an array would require the code to do manual copies to add elements to the path. \$\endgroup\$ Commented Apr 10, 2014 at 1:27
  • \$\begingroup\$ @DavidHarkness - I was not particularly clear on the int[] stack, from a performance perspective, I know it will be faster than all the autoboxing going on. Explaining how I would do it is hard without actually doing it ;-) So I just 'recommended it'. \$\endgroup\$ Commented Apr 10, 2014 at 1:30
  • \$\begingroup\$ @rolfl is my worst time complexity analysis right? \$\endgroup\$ Commented Apr 10, 2014 at 1:39
3
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Duh, I missed that in my review, and complexity analysis... hmmm. \$\endgroup\$ Commented Apr 10, 2014 at 1:57
  • \$\begingroup\$ @200_success so doing something like curList.remove(curList.size()-1); would be better, right? \$\endgroup\$ Commented Apr 10, 2014 at 1:59
  • \$\begingroup\$ That could work too, but lacks clarity. Ideally, you want to think of it as a stack with push() / pop() operations, though. \$\endgroup\$ Commented Apr 10, 2014 at 2:00
  • \$\begingroup\$ @bazang I'm curious what your 110 test cases looked like, and how it missed this bug. \$\endgroup\$ Commented Apr 10, 2014 at 2:02
  • \$\begingroup\$ @200_success it's an online judge, and it mentions how many test cases it passed. There are no duplicates, and there can be negative values. \$\endgroup\$ Commented Apr 10, 2014 at 2:05
1
\$\begingroup\$

  • 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.

\$\endgroup\$
4
  • \$\begingroup\$ It does allow negatives. But my question to you is, hypothetically speaking, would you still hire me and over look my naive mistakes(entry-level, fresh college graduate)? (I will read the Google's style guide right now, and I promise you will see improvements). \$\endgroup\$ Commented Apr 10, 2014 at 1:38
  • \$\begingroup\$ A style different from mine (you're still consistent which is key) would never raise a red flag for me in hiring. Inconsistencies in formatting of an offline code submission--which is not the case here--would merely prompt some probing from me. I know school rarely teaches these concepts, and they are trivial to pick up if you want to. Now if I hired you, gave you our style guide, and corrected you a few times, and you continued to violate that style, I would have a heart-to-heart with you over coffee or a beer as a last resort. \$\endgroup\$ Commented Apr 10, 2014 at 1:50
  • \$\begingroup\$ I like you, thanks for your response sir. Would it be a personal question to ask where you are employed? Feel free to ignore. \$\endgroup\$ Commented Apr 10, 2014 at 1:56
  • \$\begingroup\$ We've crossed into forum territory which is discouraged on StackExchange to keep the focus on the real topic--Q&A and (here) the code--so I'll delete this comment shortly (as I recommend you do too). But in case it helps, I can say with certainty that this advice is applied at Google. How you think overwhelms what you know and which style you follow. Peruse Programmers.SE for far more comprehensive advice on this topic. Also, on all SE sites +1 is the accepted substitute for "thanks", but I won't hold it against you. ;) \$\endgroup\$ Commented Apr 10, 2014 at 2:11
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Or you could use arrayList.remove(arrayList.lastIndexOf(object)) \$\endgroup\$ Commented Aug 24, 2014 at 14:57
0
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ I suspect TreeNode was supplied by the problem description, but I still disagree with using an array in place of left and right. \$\endgroup\$ Commented Apr 10, 2014 at 1:23
  • \$\begingroup\$ @AJMansfield TreeNode was provided by the problem description. \$\endgroup\$ Commented Apr 10, 2014 at 1:40

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.