Print all paths from root to leaf nodes in given binary tree

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

 

For example, consider below binary tree


          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 –

 

Download   Run Complete Code

 
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

Notify of
avatar
Sort by:   newest | oldest | most voted
TheDarkKnight
Guest
TheDarkKnight

Please share the iterative approach.

Arun
Guest
Arun
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… Read more »
wpDiscuz