Print all nodes of a perfect binary tree in specific order

Given a perfect binary tree, write an efficient algorithm to print all nodes of it in specific order. We need to print nodes of every level in alternating left and right.

 

For example, there are two ways to print below tree –
 

Variation 1: Print Top-Down

(1, 2, 3, 4, 7, 5, 6, 8, 15, 9, 14, 10, 13, 11, 12)
 

Variation 2: Print Bottom-Up

(8, 15, 9, 14, 10, 13, 11, 12, 4, 7, 5, 6, 2, 3, 1)

 

Berfect Binary Tree

 


 

Variation 1: Print Top-Down

 

The idea is to do modify level order traversal by maintaining two queues. We process two nodes at a time each from one queue and enqueue left and right child of first popped node into the first queue and right and left child of second popped node into the second queue.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 
 

Variation 2: Print Bottom-up

 

The idea is to store nodes of every level in desired order in a map and finally print nodes from the map for each level starting from last level to first level.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
Exercise: Modify the solution to print using only one queue

 
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
Abhishek
Guest
Abhishek

What if the binary tree is right skewed?
The flow doesn’t enter the outer while loop itself. Wrong output I guess.
https://ideone.com/AMWrer
Please explain

wpDiscuz