geeksforgeeks

// CPP program to print Zig-Zag traversal 
// in groups of size 2. 
#include <iostream> 
#include <stack> 
#include <queue> 
  
using namespace std; 
  
#define LEFT 0 
#define RIGHT 1 
#define ChangeDirection(Dir) ((Dir) = 1 - (Dir)) 
  
// A Binary Tree Node 
struct node  
{ 
    int data; 
    struct node *left, *right; 
}; 
  
// Utility function to create a new tree node  
node* newNode(int data)  
{  
    node* temp = new node;  
    temp->data = data;  
    temp->left = temp->right = NULL;  
    return temp;  
}  
  
/* Function to print the level order of  
   given binary tree. Direction of printing  
   level order traversal of binary tree changes  
   after every two levels */
void modifiedLevelOrder(struct node *root) 
{ 
    if (!root) 
        return ; 
      
    int dir = LEFT; 
    struct node *temp; 
    queue <struct node *> Q; 
    stack <struct node *> S; 
  
    S.push(root); 
      
    // Run this while loop till queue got empty 
    while (!Q.empty() || !S.empty()) 
    { 
        while (!S.empty()) 
        { 
            temp = S.top(); 
            S.pop(); 
            cout << temp->data << " "; 
              
            if (dir == LEFT) { 
                if (temp->left) 
                    Q.push(temp->left); 
                if (temp->right) 
                    Q.push(temp->right); 
            }  
            /* For printing nodes from right to left, 
            push the nodes to stack instead of printing them.*/
            else { 
                if (temp->right) 
                    Q.push(temp->right); 
                if (temp->left) 
                    Q.push(temp->left); 
            } 
        } 
          
        cout << endl; 
          
            // for printing the nodes in order 
            // from right to left 
        while (!Q.empty()) 
        { 
            temp = Q.front(); 
            Q.pop(); 
            cout << temp->data << " "; 
              
            if (dir == LEFT) { 
                if (temp->left) 
                    S.push(temp->left); 
                if (temp->right) 
                    S.push(temp->right); 
            } else { 
                if (temp->right) 
                    S.push(temp->right); 
                if (temp->left) 
                    S.push(temp->left); 
            } 
        } 
        cout << endl; 
  
        // Change the direction of traversal. 
        ChangeDirection(dir); 
    } 
} 
  
// Driver program to test above functions  
int main()  
{  
    // Let us create binary tree  
    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(3);  
    root->left->right->right = newNode(1);  
    root->right->left->left = newNode(4);  
    root->right->left->right = newNode(2);  
    root->right->right->left = newNode(7);  
    root->right->right->right = newNode(2);  
    root->left->right->left->left = newNode(16);  
    root->left->right->left->right = newNode(17);  
    root->right->left->right->left = newNode(18);  
    root->right->right->left->right = newNode(19);  
  
    modifiedLevelOrder(root);  
  
    return 0;  
} 

#include <stdio.h> 
int main(void) 
{ 
    if (printf("Hello World")) { 
    } 
}