#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;


typedef struct Node{
    struct Node *left, *right;
    int item;
}Node;

Node *root = NULL;


Node *createNode(int value){
    Node *newNode = (Node*)malloc(sizeof(Node));

    if(newNode){ newNode->left = NULL, newNode->right = NULL, newNode->item = value;}
    return newNode;
}

void printLevels(Node *root){

    queue<Node*> q;

    q.push(root);
    int currLevel = 0;
    while(q.size()){
        int N = q.size();
        vector<Node*> q2;
        for(int i= 0; i < N; ++i){
            Node *n = q.front(); q.pop();
            q2.push_back(n);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        if (currLevel % 2 == 0) {
            for (int i = q2.size() - 1; i >= 0; --i)
                cout << q2[i]->item << " ";
        } else {
            for (int i = 0; i < (int)q2.size(); ++i)
                cout << q2[i]->item << " ";
        }
        cout << endl;
        ++currLevel;
    }


}

void insertNode(Node *node){

    Node **tmp = &root;

    while(*tmp){
        if( (*tmp)->item > node->item){
            tmp = &((*tmp)->left);
        }
        else if( (*tmp)->item < node->item){
            tmp = &((*tmp)->right);
        }
    }
    *tmp = node;
}

int main(void){

    insertNode(createNode(10));
    insertNode(createNode(3));
    insertNode(createNode(12));
    insertNode(createNode(2));
    insertNode(createNode(4));
    insertNode(createNode(11));
    insertNode(createNode(14));

    printLevels(root);
    return 0;
}