Perfect Binary Tree Specific Level Order Traversal | Set 2 | C ++ program for special order traversal ; A binary tree node has data , pointer to left child and a pointer to right child ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Function body ; Create a queue and enqueue left and right children of root ; We process two nodes at a time , so we need two variables to store two front items of queue ; traversal loop ; Pop two items from queue ; Push first and second node 's chilren  in reverse order ; If first and second have grandchildren , enqueue them in specific order ; Given a perfect binary tree , print its nodes in specific level order ; create a stack and push root ; Push level 1 and level 2 nodes in stack ; Since it is perfect Binary Tree , right is not checked ; Do anything more if there are nodes at next level in given perfect Binary Tree ; Finally pop all Nodes from stack and prints them . ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * newNode ( int data ) { Node * node = new Node ; node -> data = data ; node -> right = node -> left = NULL ; return node ; } void printSpecificLevelOrderUtil ( Node * root , stack < Node * > & s ) { if ( root == NULL ) return ; queue < Node * > q ; q . push ( root -> left ) ; q . push ( root -> right ) ; Node * first = NULL , * second = NULL ; while ( ! q . empty ( ) ) { first = q . front ( ) ; q . pop ( ) ; second = q . front ( ) ; q . pop ( ) ; s . push ( second -> left ) ; s . push ( first -> right ) ; s . push ( second -> right ) ; s . push ( first -> left ) ; if ( first -> left -> left != NULL ) { q . push ( first -> right ) ; q . push ( second -> left ) ; q . push ( first -> left ) ; q . push ( second -> right ) ; } } } void printSpecificLevelOrder ( Node * root ) { stack < Node * > s ; s . push ( root ) ; if ( root -> left != NULL ) { s . push ( root -> right ) ; s . push ( root -> left ) ; } if ( root -> left -> left != NULL ) printSpecificLevelOrderUtil ( root , s ) ; while ( ! s . empty ( ) ) { cout << s . top ( ) -> data << " ▁ " ; s . pop ( ) ; } } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; cout << " Specific ▁ Level ▁ Order ▁ traversal ▁ of ▁ binary ▁ " " tree ▁ is ▁ STRNEWLINE " ; printSpecificLevelOrder ( root ) ; return 0 ; }