#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){

    vector<Node*> q;

    q.push_back(root);
    int currLevel = 0;
    while(q.size()){
        int N = q.size();
        vector<Node*> q2;
        for(int i=N - 1; i >= 0; --i){
            Node *n = q[i];

            cout << n->item << " ";
            if(currLevel % 2 == 0){
                if(n->right) q2.push_back(n->right);
                if(n->left) q2.push_back(n->left);
            }
            else{
                if(n->left) q2.push_back(n->left);
                if(n->right) q2.push_back(n->right);
         }
        }
        cout << endl;
        ++currLevel;
        q = q2;
    }


}

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;
}