Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# Print All Paths of a Tree Problem

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

#### Solution

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

``````
// -------- START --------

void getAllPaths(TreeNode *root, vector ¤tPathValues, vector > &allPaths){

// If we reached at leaf node
if(root->left_ptr == NULL && root->right_ptr == NULL){
currentPathValues.push_back(root->val);
allPaths.push_back(currentPathValues);
currentPathValues.pop_back();
return;
}
// Push current node's value in current path
currentPathValues.push_back(root->val);

// Recursive call for left subtree
if(root->left_ptr != NULL){
getAllPaths(root->left_ptr, currentPathValues, allPaths);
}

// Recusrive call for right subtree
if(root->right_ptr != NULL){
getAllPaths(root->right_ptr, currentPathValues, allPaths);
}

// Pop last added value i.e. current node's value
currentPathValues.pop_back();
}

vector > allPathsOfABinaryTree(TreeNode* root){
vector > allPaths;
// empty or null tree check
if(root == NULL) {
return allPaths;
}
vector currentPathValue;
getAllPaths(root, currentPathValue, allPaths);
return allPaths;
}

// -------- END --------
``````

### Try yourself in the Editor

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

# Print All Paths of a Tree Problem

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

#### Solution

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

``````
// -------- START --------

void getAllPaths(TreeNode *root, vector ¤tPathValues, vector > &allPaths){

// If we reached at leaf node
if(root->left_ptr == NULL && root->right_ptr == NULL){
currentPathValues.push_back(root->val);
allPaths.push_back(currentPathValues);
currentPathValues.pop_back();
return;
}
// Push current node's value in current path
currentPathValues.push_back(root->val);

// Recursive call for left subtree
if(root->left_ptr != NULL){
getAllPaths(root->left_ptr, currentPathValues, allPaths);
}

// Recusrive call for right subtree
if(root->right_ptr != NULL){
getAllPaths(root->right_ptr, currentPathValues, allPaths);
}

// Pop last added value i.e. current node's value
currentPathValues.pop_back();
}

vector > allPathsOfABinaryTree(TreeNode* root){
vector > allPaths;
// empty or null tree check
if(root == NULL) {
return allPaths;
}
vector currentPathValue;
getAllPaths(root, currentPathValue, allPaths);
return allPaths;
}

// -------- END --------
``````

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Hosted By
Ryan Valles
Founder, Interview Kickstart
Accelerate your Interview prep with Tier-1 tech instructors
360° courses that have helped 14,000+ tech professionals
100% money-back guarantee*