# Print all nodes of a perfect binary tree in specific order

Given a 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(nlog(n)) and auxiliary space used by the program is O(n).

Exercise: Modify the solution to print using only one queue

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest

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