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 &currentPathValues, vector<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<vector > allPathsOfABinaryTree(TreeNode* root){
    vector<vector > allPaths;
    // empty or null tree check
    if(root == NULL) {
        return allPaths;
    }
    vector currentPathValue;
    getAllPaths(root, currentPathValue, allPaths);
    return allPaths;
}

// -------- END --------