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

For example, consider below binary tree

There are five leaf to root path in above binary tree –

4 -> 2 -> 1

5 -> 2 -> 1

8 -> 6 -> 3 -> 1

9 -> 6 -> 3 -> 1

7 -> 3 -> 1

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 in reverse order.

Here’s a C++ program that demonstrates it:

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 48 49 50 51 52 53 |
// 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); } // Print path present in the vector in reverse order (leaf to root node) void printPath(vector<int> const &path) { for (int i = path.size() - 1; i > 0; i--) cout << path.at(i) << " -> "; cout << path.at(0) << endl; } // Recursive function to print all paths from leaf to root node void printLeafToRootPaths(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)) printPath(path); // recurse for left and right subtree printLeafToRootPaths(node->left, path); printLeafToRootPaths(node->right, path); // remove current node after left and right subtree are done path.pop_back(); } // Main function to print all paths from leaf to root node void printLeafToRootPaths(Node* node) { // vector to store left to root path vector<int> path; // call recursive function printLeafToRootPaths(node, path); } |

`Output:`

4 -> 2 -> 1

5 -> 2 -> 1

8 -> 6 -> 3 -> 1

9 -> 6 -> 3 -> 1

7 -> 3 -> 1

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 implementation of above problem.

2. Modify the solution to print leaf to root path 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.