# 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)

### 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 –

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 –

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 🙂

Get great deals at Amazon

### Leave a Reply

Subscribe
Notify of
Guest
nitinJ

Top down approach using single queue:
https://ideone.com/cKHzi2

Bottom up approach using single queue:
https://ideone.com/nuUNJr

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