Given a binary tree, write an efficient algorithm to print all paths from root node to every leaf node in it.

1

/ \

/ \

2 3

/ \ / \

4 5 6 7

/ \

8 9

There are four root to leaf paths –

1 -> 2 -> 4

1 -> 2 -> 5

1 -> 3 -> 6 -> 8

1 -> 3 -> 7 -> 9

The idea is to traverse the tree in preorder fashion and store every encountered node in current path from root to leaf in a vector. If we encounter a leaf node, we print all nodes present in the vector. Below is C++ implementation of the idea –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to check if given node is a leaf node or not bool isLeaf(Node* node) { return (node->left == nullptr && node->right == nullptr); } // Recursive function to find paths from root node to every leaf node void printRootToleafPaths(Node* node, vector<int> &path) { // base case if (node == nullptr) return; // include current node to path vector path.push_back(node->data); // if leaf node is found, print the path if (isLeaf(node)) { for (int data: path) cout << data << " "; cout << endl; } // recurse for left and right subtree printRootToleafPaths(node->left, path); printRootToleafPaths(node->right, path); // remove current node after left and right subtree are done path.pop_back(); } // Main function to print paths from root node to every leaf node void printRootToleafPaths(Node* node) { // vector to store root to leaf path vector<int> path; printRootToleafPaths(node, path); } |

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

**Exercise:**

1. Write iterative solution of above problem.

2. Modify the solution to print root to leaf paths having sum of nodes equal to a given number.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Please share the iterative approach.

Thanks a lot Arun, we have updated the code.