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:
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
wpDiscuz