Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Given a binary tree, return all paths from root to leaf.

**Example One**

Input:

Output: [[1, 2, 4], [1, 2, 5], [1, 3, 6], [1, 3, 7]]

There are four leafs in the given graph, so we have four paths: from the root to every leaf. Each path is a list of the values from the tree nodes on the path, and we have four lists. They can go in any order.

**Example Two**

Input:

Output: [[10, 20, 40], [10, 20, 50], [10, 30]]

There are 3 paths in the tree.

The leftmost path contains values: 10 -> 20 -> 40

The rightmost path contains values: 10 -> 30

The other path contains values: 10 -> 20 -> 50

The order of the paths (order of the lists in the outer list) does not matter, so [[10, 30], [10, 20, 40], [10, 20, 50]] is another correct answer.

**Notes**

Input Parameters: Function has one argument, root of the input tree.

Output: Return a list of integer lists.

**Constraints:**

• 0

• -10^9

We provided one solution.

This problem asked to return all the paths from the root node to the leaf nodes. So, if there are K leaf nodes, there will be K paths. To find a path, we have used depth first search technique. The approach is described below:

a. If the root is null, there are no paths. Return empty list.

b. If the root node is also the only leaf node, return a list containing the root as a single path.

c. Append current node value in a temporary list and go to left child

d. If current node is a leaf node, append its value to the temporary list. Append the temporary list (the list itself, not its values) to the outer result list. Otherwise repeat step c. Remove current node value from the temporary list.

e. Go to the right child and repeat step c until you reach step d.

f. Remove current node value from the temporary list.

We did this using backtracking.

Time Complexity (assuming that input arguments are already

given and excluding time used in the declaration of output):

O(N+M) where N is the number of nodes and M is the number of edges.

As to print all the paths, we have to traverse the whole tree at least once and the tree contains N nodes and M edges, hence the computation complexity is O(N+M).

**Time Complexity:**

O((N+1)/2 log (N+1)) where N denotes the number of nodes in the tree.

Time complexity assuming that input arguments are already

given and excluding time used in the declaration of output is O(N + M) and to read input arguments it will take O( N+ M) time. Declaration of output takes O((N+1)/2 log (N+1)) times in worst case as if the input tree is a complete binary tree, there will be (N+1)/2 leaves and in each path there will be log N nodes. So, the size of the output list will be O((N+1)/2 log (N+1)). Hence time complexity will be O(N+M) + O(N+M) + O((N+1)/2 log (N+1)) → O((N+1)/2 log (N+1)).

**Auxiliary Space:**

O((N+1)/2 log (N+1)) where N denotes the number of nodes.

In the worst case, the size of the output list can be O((N+1)/2 log (N+1)) and recursion takes O(N) stack memory, auxiliary space is O((N+1)/2 log (N+1)) + O(N) → O((N+1)/2 log (N+1)).

**Space Complexity:**

O((N+1)/2 log (N+1)) where N denotes the number of nodes.

As to store input tree it will take O(N+ M) space, auxiliary

space is O((N+1)/2 log (N+1)) and to return the result it takes O((N+1)/2 log (N+1)) memory, hence space complexity is O(N+M) + O((N+1)/2 log (N+1)) + O((N+1)/2 log (N+1)) → O((N+1)/2 log (N+1)).

Note: Input and Output will already be taken care of.