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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
// Function to print all nodes of a given binary tree in specific // order from top to bottom void printNodes(Node* root) { // return is tree is empty if (root == nullptr) return; // print root node cout << root->key << " "; // create an two empty queues and enqueue root's left and // right child respectively queue<Node *> Q1, Q2; Q1.push(root->left); Q2.push(root->right); // run till queue is not empty while (!Q1.empty()) { // calculate number of nodes in current level int n = Q1.size(); // process every node of current level while (n--) { // pop front node from first queue and print it Node* x = Q1.front(); Q1.pop(); cout << x->key << " "; // push left and right child of x to first queue if (x->left) Q1.push(x->left); if (x->right) Q1.push(x->right); // pop front node from second queue and print it Node* y = Q2.front(); Q2.pop(); cout << y->key << " "; // push right and left child of y to second queue if (y->right) Q2.push(y->right); if (y->left) Q2.push(y->left); } } } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
// Function to print all nodes of a given binary tree in // specific order from bottom to top void printNodes(Node* root) { // return is tree is empty if (root == nullptr) return; // start with level 1 (of root node) int level = 1; // create an empty multi-map of integers (every key can be // associated with multiple values) map<int, vector<int>> map; // insert root node at first level map[level].push_back(root->key); // create an two empty queues and enqueue root's left and // right child respectively queue<Node *> Q1, Q2; Q1.push(root->left); Q2.push(root->right); // run till queue is not empty while (!Q1.empty()) { // increment level by 1 level++; // calculate number of nodes in current level int n = Q1.size(); // process every node of current level while (n--) { // pop front node from first queue and insert it into the map Node* x = Q1.front(); Q1.pop(); map[level].push_back(x->key); // push left and right child of x to first queue if (x->left) Q1.push(x->left); if (x->right) Q1.push(x->right); // pop front node from second queue and insert it into the map Node* y = Q2.front(); Q2.pop(); map[level].push_back(y->key); // push right and left child of y to second queue if (y->right) Q2.push(y->right); if (y->left) Q2.push(y->left); } } // iterate through the map using reverse iterator and // print all nodes present in very level for (auto it = map.rbegin(); it != map.rend(); it++) { for (int i: it->second) cout << i << " "; } } |

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

**Thanks for reading.**

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 🙂

## Leave a Reply

Top down approach using single queue:

https://ideone.com/cKHzi2

Bottom up approach using single queue:

https://ideone.com/nuUNJr

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

Hello,

Thank you for sharing your concerns. Please note that the solution is valid for only perfect binary trees.

what if we use a deque and just use pop front and popback at a given level alternatively?