educative.io

Isn't my algorithm O(N) time complexity for All Paths for a Sum? Compare to O(N lgN) of given solution (i.e. why backtracking is preferred, when we can solve in O(N)?)

Courses
,
#1

Please correct me if I am wrong but isn’t my algorithm O(N) (where N is # of nodes in the given tree).
Following is my algorithm, the only difference from solution (provided in the tutorial) is I am updating ArrayList current path (‘cpath’ in my code) only when I find a path.

public static List<List> findPaths(TreeNode root, int sum) {
List<List> allpaths = new ArrayList<List>();
List cpath = new ArrayList();
dfs(root, sum, cpath, allpaths);
return allpaths;
}

private static void dfs(TreeNode root, int sum, List cpath, List<List> allpaths){
if(root == null){
return;
}
if(root.val == sum && root.left == null && root.right == null){
cpath.add(root.val);
allpaths.add(cpath);
}
List temp = new ArrayList();
temp.addAll(cpath);
temp.add(root.val);
dfs(root.left, sum-root.val, temp, allpaths);
dfs(root.right, sum-root.val, temp, allpaths);
}

1 Like
#2

Either way (with or without backtrack) the code run time complexity is O(N). N being the number of nodes in the tree. In this case, in my humble opinion, that official backtracking code is a poor choice

#3

But your space complexity is going to be terrible. IMHO.
i.e for each node you will copy existing path.
N(total nodes) * log N(max nodes) * N/2(total paths) = N2 * log N

#4

Nope, your solution’s time complexity is not O(N). It has the same time complexity as the original solution. Your space complexity is worse as @Gaurav7 suggested, but it should be O(NlogN) not O(N^2logN).

The original solution: Modifying the current path list is O(1) at each node and it’s O(N) overall. Appending to all paths list at each leaf node requires a copy of the current path list first, the list creation is O(logN) and list appending is O(logN) for each leaf, so O(logN) + O(logN) which is O(logN). Then overall the appending is O(NlogN).

Yours: As you will need to create a copy of the current path list at each node, the list creation would take O(NlogN) when you traverse all nodes. The difference is that the appending to all paths list at each leaf node will skip the list creation.

1 Like