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.

Here you go – http://ideone.com/nArto6

The idea is to do iterative inorder traversal of the tree and while doing so, we maintain a map that contains (child, parent) pair for encountered nodes. Now if a leaf node is encountered, we can easily print leaf-to-root path using that map.

Hope this helps and thank you 🙂

Hey,

Thank you so much 🙂

I should have been more clear in my query. Actually I found a based solution but I was trying to avoid using it.

In other words I was looking a solution based on iterative inorder traversal but using only STL stack(s) and/or queue(s).

Following is the code I was working upon:

http://ideone.com/5cqQov (Pasting the link for code for better indentation)

Please help me to correct the code.

Thanks for your help.

Pure stack-based or queue-based approach is not ideally possible unless we maintain a parent pointer in each of the tree nodes.. But we came up with a workaround.. We can store root to leaf path in a string as we traverse the tree iteratively.

We have published the solution here. Hope this helps 🙂

Instead of copy vector evetytime, its better we send a reference and pop the element after both left and right are done

void inorderRecursive(Node *root, vector &path) {

if (root == NULL) return;

if (root->left == NULL && root->right == NULL) {

for(auto i : path) {

cout << i << " ";

}

cout <data <data);

inorderRecursive(root->left, path);

inorderRecursive(root->right, path);

path.pop_back();

}

Thanks a lot Arun, we have updated the code.