Print leaf to root path for every leaf node in a binary tree

Given a binary tree, write an iterative algorithm to print leaf to root path for every leaf node of binary tree. Use of Recursion is prohibited.

 

For example, consider below binary tree
 

Print Leaf to Root Path
 

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

 


 

Since we’re not allowed to use recursion, we can do postorder iterative traversal of the tree and while doing so, we maintain a map that contains (child, parent) pair for every encountered node. Now if a leaf node is encountered, we can easily print leaf to root path using that map as shown below:

C++

Download   Run Complete Code

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) but it needs extra O(n) space for the map. Unless we maintain a parent pointer in each of the tree nodes, the problem seems very difficult to solve without using any additional extra space apart from stack.

There is one workaround that doesn’t involve maintaining a parent pointer or use of any additional extra space. We can store path from root to leaf in a string as we traverse the tree iteratively and print the path whenever we encounter any leaf node.

C++

Download   Run Complete Code

Output:

4 -> 2 -> 1
5 -> 2 -> 1
8 -> 6 -> 3 -> 1
9 -> 6 -> 3 -> 1
7 -> 3 -> 1

Exercise:

1. Write recursive 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

Notify of
avatar
wpDiscuz