#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <stdbool.h>

struct tree{
    int info;
    struct tree *left;
    struct tree *right;
};
struct q_node;

struct queue{
    struct q_node *first;
    struct q_node *last;
};

struct q_node{
    struct tree *ptr;
    struct q_node *next;
};
/*
//debug
void print_queue(struct queue *q){
    for (struct q_node *tmp = q->first; tmp != NULL; tmp = tmp->next)
        printf("%d ", tmp->ptr->info);
    printf("\n");
    fflush(stdout);
}
//enddebug
*/

struct q_node *init_q_node(struct tree *ptr, struct q_node *next){
    struct q_node *tmp = (struct q_node *) malloc(sizeof(struct q_node));
    tmp->ptr = ptr;
    tmp->next = next;
    return tmp;
}

void push_back(struct queue *q, struct q_node *node){

    if (q->first == NULL)
        q->first = q->last = node;

    else {
        q->last->next = node;
        q->last = q->last->next;
    }
}


struct q_node *pop(struct queue *q){
    /*debug*/
/*
    printf("before:\n");
    print_queue(q);

*/

    if (q->first == NULL)
        return NULL;

    struct q_node *cur_ptr = q->first;
    q->first = q->first->next;

    if (cur_ptr == q->last)
        q->last = NULL;

   /* printf("after:\n");
    print_queue(q);*/
    return cur_ptr;
};

void BFS(struct queue *q){
    while (q->first != NULL){
        struct q_node *Node = pop(q);
        struct tree *cur_el = (Node->ptr);

        if (cur_el->left != NULL)
            push_back(q, init_q_node(cur_el->left, NULL));
        if (cur_el->right != NULL)
            push_back(q, init_q_node(cur_el->right, NULL));

        printf("%i ", Node->ptr->info);
//        free(Node->ptr);
        free(Node);
    }
}

struct tree *tree_init(int info){
    struct tree *tmp = (struct tree*) malloc(sizeof(struct tree));
    tmp->info = info;
    tmp->left = NULL;
    tmp->right = NULL;
    return tmp;
}

void Delete_tree(struct tree * root){
    if (root->right != NULL)
        Delete_tree(root->right);

    if (root->left != NULL)
        Delete_tree(root->left);

    free(root);
}

int main(){

    FILE *fin = fopen("input.txt", "r");

    int numb, key;
    printf("print number of elements: \n");
    fscanf(fin, "%i", &numb);

    printf("print key of your tree: \n");
    fscanf(fin, "%i", &key);

    struct tree *tmp, *root;
    root = tree_init(key);

    int count;
    printf("print elements of your tree: \n");
    for (int i = 0; i < numb; i++){
        fscanf(fin, "%i", &count);
        tmp = root;
        while ( true ){
            if (count >= tmp->info){
                if (tmp->right != NULL)
                    tmp = tmp->right;
                else {
                    tmp->right = tree_init(count);
                    break;
                }
            }
            else {
                if (tmp->left != NULL)
                    tmp = tmp->left;
                else {
                    tmp->left = tree_init(count);
                    break;
                }
            }
        }
    }

    tmp = root;
    struct queue *q = (struct queue*) malloc(sizeof(struct queue));
    q->first = q->last = NULL;
    push_back(q, init_q_node(tmp, NULL));
    BFS(q);

    Delete_tree(root);
    free(q);
    getch();
    return 0;
}