# Perfect Binary Tree Specific Level Order Traversal

Given a Perfect Binary Tree like below:

Print the level order of nodes in following specific manner:

`  1 2 3 4 7 5 6 8 15 9 14 10 13 11 12 16 31 17 30 18 29 19 28 20 27 21 26  22 25 23 24`

i.e. print nodes in level order but nodes should be from left and right side alternatively. Here 1st and 2nd levels are trivial.
While 3rd level: 4(left), 7(right), 5(left), 6(right) are printed.
While 4th level: 8(left), 15(right), 9(left), 14(right), .. are printed.
While 5th level: 16(left), 31(right), 17(left), 30(right), .. are printed.

We strongly recommend to minimize your browser and try this yourself first.

In standard Level Order Traversal, we enqueue root into a queue 1st, then we dequeue ONE node from queue, process (print) it, enqueue its children into queue. We keep doing this until queue is empty.

Approach 1:
We can do standard level order traversal here too but instead of printing nodes directly, we have to store nodes in current level in a temporary array or list 1st and then take nodes from alternate ends (left and right) and print nodes. Keep repeating this for all levels.
This approach takes more memory than standard traversal.

Approach 2:
The standard level order traversal idea will slightly change here. Instead of processing ONE node at a time, we will process TWO nodes at a time. And while pushing children into queue, the enqueue order will be: 1st node’s left child, 2nd node’s right child, 1st node’s right child and 2nd node’s left child.

`/* C++ program for special order traversal */`
`#include <iostream>`
`#include <queue>`
`using` `namespace` `std;`
`/* A binary tree node has data, pointer to left child`
`   ``and a pointer to right child */`
`struct` `Node`
`{`
`    ``int` `data;`
`    ``Node *left;`
`    ``Node *right;`
`};`
`/* Helper function that allocates a new node with the`
`   ``given data and NULL left and right pointers. */`
`Node *newNode(``int` `data)`
`{`
`    ``Node *node = ``new` `Node;`
`    ``node->data = data;`
`    ``node->right = node->left = NULL;`
`    ``return` `node;`
`}`
`/* Given a perfect binary tree, print its nodes in specific`
`   ``level order */`
`void` `printSpecificLevelOrder(Node *root)`
`{`
`    ``if` `(root == NULL)`
`        ``return``;`
`    ``// Let us print root and next level first`
`    ``cout << root->data;`
`    ``// / Since it is perfect Binary Tree, right is not checked`
`    ``if` `(root->left != NULL)`
`      ``cout << ``" "` `<< root->left->data << ``" "` `<< root->right->data;`
`    ``// Do anything more if there are nodes at next level in`
`    ``// given perfect Binary Tree`
`    ``if` `(root->left->left == NULL)`
`        ``return``;`
`    ``// Create a queue and enqueue left and right children of root`
`    ``queue <Node *> q;`
`    ``q.push(root->left);`
`    ``q.push(root->right);`
`    ``// We process two nodes at a time, so we need two variables`
`    ``// to store two front items of queue`
`    ``Node *first = NULL, *second = NULL;`
`    ``// traversal loop`
`    ``while` `(!q.empty())`
`    ``{`
`       ``// Pop two items from queue`
`       ``first = q.front();`
`       ``q.pop();`
`       ``second = q.front();`
`       ``q.pop();`
`       ``// Print children of first and second in reverse order`
`       ``cout << ``" "` `<< first->left->data << ``" "` `<< second->right->data;`
`       ``cout << ``" "` `<< first->right->data << ``" "` `<< second->left->data;`
`       ``// If first and second have grandchildren, enqueue them`
`       ``// in reverse order`
`       ``if` `(first->left->left != NULL)`
`       ``{`
`           ``q.push(first->left);`
`           ``q.push(second->right);`
`           ``q.push(first->right);`
`           ``q.push(second->left);`
`       ``}`
`    ``}`
`}`
`/* Driver program to test above functions*/`
`int` `main()`
`{`
`    ``//Perfect Binary Tree of Height 4`
`    ``Node *root = newNode(1);`
`    ``root->left        = newNode(2);`
`    ``root->right       = newNode(3);`
`    ``root->left->left  = newNode(4);`
`    ``root->left->right = newNode(5);`
`    ``root->right->left  = newNode(6);`
`    ``root->right->right = newNode(7);`
`    ``root->left->left->left  = newNode(8);`
`    ``root->left->left->right  = newNode(9);`
`    ``root->left->right->left  = newNode(10);`
`    ``root->left->right->right  = newNode(11);`
`    ``root->right->left->left  = newNode(12);`
`    ``root->right->left->right  = newNode(13);`
`    ``root->right->right->left  = newNode(14);`
`    ``root->right->right->right  = newNode(15);`
`    ``root->left->left->left->left  = newNode(16);`
`    ``root->left->left->left->right  = newNode(17);`
`    ``root->left->left->right->left  = newNode(18);`
`    ``root->left->left->right->right  = newNode(19);`
`    ``root->left->right->left->left  = newNode(20);`
`    ``root->left->right->left->right  = newNode(21);`
`    ``root->left->right->right->left  = newNode(22);`
`    ``root->left->right->right->right  = newNode(23);`
`    ``root->right->left->left->left  = newNode(24);`
`    ``root->right->left->left->right  = newNode(25);`
`    ``root->right->left->right->left  = newNode(26);`
`    ``root->right->left->right->right  = newNode(27);`
`    ``root->right->right->left->left  = newNode(28);`
`    ``root->right->right->left->right  = newNode(29);`
`    ``root->right->right->right->left  = newNode(30);`
`    ``root->right->right->right->right  = newNode(31);`
`    ``cout << ``"Specific Level Order traversal of binary tree is \n"``;`
`    ``printSpecificLevelOrder(root);`
`    ``return` `0;`
`}`

Output:

```Specific Level Order traversal of binary tree is
1 2 3 4 7 5 6 8 15 9 14 10 13 11 12 16 31 17 30 18 29 19 28 20 27 21 26 22 25 23 24```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

rakesh