Grokking Tree Coding Patterns for Interviews

0% completed

​

Solution: All Paths for a Sum

Problem Statement

Given a binary tree and a number ‘S’, find all paths from root-to-leaf such that the sum of all the node values of each path equals ‘S’.

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

Solution

This problem follows the Binary Tree Path Sum problem. We can follow the same DFS approach. There will be two differences though:

Every time we find a root-to-leaf path, we will store it in a list. We will traverse all paths and will not stop processing after finding the first path

.....

.....

.....

Like the course? Get enrolled and start learning!
J

Jasman Arora

· 4 years ago

Can you please explain this part?

remove the current node from the path to backtrack,

we need to remove the current node while we are going up the recursive call stack.

del currentPath[-1] Why do we need to remove the current node in the end?

Show 1 reply
D

dg

· 4 years ago

I copy and pasted your solution in for "All Paths for a Sum" and the code below does not seem to work. It just outputs two empty arrays. Even using the Dequeue lib (which, seeing as I generally can't install libs during an interview, it feels odd to see these peppered in), it does not work. Anyone else seen this?

Show 5 replies
S

Siew Lee

· 3 years ago

allPaths.append(list(currentPath)) <- why do we add list() here?

Show 1 reply
D

Dylan Asoh

· 4 years ago

Why do we need to cast the currentPath list to a list if it's already a list? If we don't cast it the list is empty for some reason.

Show 3 replies
Y

Yogi Paturu

· 5 years ago

In the JS solution, what's the point of using deque? Wouldn't an array be fine here, since array push and pop are O(1) operations

Show 1 reply
M

Max Boykin

· 3 years ago

If the tree is unbalanced, couldn't the space complexity still be O(N^2)? If the tree is balanced each path would have O(logN) nodes in the path but if its a linked list, it would have N nodes in the path.

S

Salah Osman

· 4 years ago

What is the time complexity for the JS solution? Wouldn't it just be O(n) ?

Arrays dynamically resize in javascript unlike in Java, pushing and popping from the tail is O(1). The length of array can be modified at run time (when necessary).

Or am I offtrack?

Show 1 reply
E

Erick Aky

· 4 years ago

So, time complexity is it O(N^2) or N(logN)?

Show 2 replies
H

hj3yoo

· 4 years ago

"The time complexity of the above algorithm is O(N^2), where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once (which will take O(N)), and for every leaf node, we might have to store its path (by making a copy of the current path) which will take O(N)."

Can someone explain why storing its path will take O(N) time complexity instead of O(1)? I can understand O(N) space complexity, but why would the time to store an array be proportional to the size of it?

Show 2 replies