educative.io

Can we not just only iterate at the leaf nodes?

Courses
,
#1 

def count_paths(root, S, prevNums = []):
  if root is None:
    return 0
  
  prevNums.append(root.val)

  numOfPaths, total = 0, 0
  # We are at a leaf node
  if root.left is None and root.right is None:
    for i in range(len(prevNums) -1, -1, -1):
      total += prevNums[i]
      
      if total == S:
        numOfPaths += 1
  else:
    numOfPaths += count_paths(root.left, S, prevNums)
    numOfPaths += count_paths(root.right, S, prevNums)

  del(prevNums[-1])
  
  return numOfPaths

Wouldn’t this achieve the same solution with a linear time complexity?

#2

Hey @Demos! So about your solution, there are a couple of things that I noticed.

Firstly, it isn’t exactly a solution running on linear time complexity but actually its time complexity will be the height of the tree times the number of nodes, which makes this approximately O(nlog(n)). This is because even though we are only iterating at the leaf nodes, it still traverses the entire tree till the deepest part and then explores each of the nodes.

Another thing is that your solution actually doesn’t cover all the cases. For example, in the test case provided, let us say we want to get the number of paths who have the sum 19. Now, over here, this would give us the output with your code: Tree has paths: 0 while the correct answer would be 1 since the nodes 7 and 12 added together give us 19.

Hope this helped!