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

#define MAXN 1000

typedef struct node
{
    int value;
    struct node *left, *right;
} node;

typedef int tip2;

typedef struct queue2
{
    tip2 arr[MAXN];
    int front, rear;
} queue2;

typedef node* tip;

typedef struct queue
{
    tip arr[MAXN];
    int front, rear;
} queue;

void push(queue *q, tip element);

tip pop(queue *q);

tip top(queue *q);

int empty(queue *q);

void push2(queue2 *q, tip2 element);

tip2 pop2(queue2 *q);

tip2 top2(queue2 *q);

int empty2(queue2 *q);

node* insertElementBST(node *root, int key);

node* deleteElementBST(node *root, int key);

node* insertElementBBST(node *root, int key);

node* deleteElementBBST(node *root, int key);

node* leftRotation(node *x);

node* rightRotation(node *x);

node* minValueNode(node *root);

node* maxValueNode(node *root);

void inorder(node *root);

//writeInorder zove inorder
void writeInorder(node *root);

void levelOrder(node *root);

//printAll zove levelOrder
void printAll(node *root);

//ispisuje oblik stabla
void myPrintTree(node *root);

void preorder(node *root);

//writePreorder zove preorder
void writePreorder(node *root);

void postorder(node *root);

//writePostorder zove postorder
void writePostorder(node *root);

//Dubina stabla do dna
int height(node *root);

//Provjera da li je stablo balansirano
int checkGood(node *root, int *flag);

//isBalanced zove checkGood, za flag = 0 nije balansirano, za flag = 1 je balansirano
void isBalanced(node *root);

int max(int a, int b);

int main()
{
    FILE *fin;
    fin = fopen("ulaz.txt", "r");
//    int n, x;
//    scanf("%d", &n);
//
//    node *bst = NULL;
//
//    for (int i = 0; i < n; ++i)
//    {
//    scanf("%d", &x);
//    insertElement(&bst, x);
//    }

    node *bst = NULL;
    int n = 0, a[100];
    while (fscanf(fin, "%d ", &a[n++]) != EOF);

    --n;
    for (int i = 0; i < n; ++i)
        bst = insertElementBBST(bst, a[i]);

    deleteElementBBST(bst, 8);
    deleteElementBBST(bst, 4);
    writeInorder(bst);
    writePreorder(bst);
    writePostorder(bst);
    printAll(bst);
    isBalanced(bst);
    myPrintTree(bst);
}

node* insertElementBST(node *root, int key)
{
    if (root == NULL)
    {
        node *nju = (node*)malloc(sizeof(node));
        nju->left = nju->right = NULL;
        nju->value = key;
        return nju;
    }

    if (key < root->value)
        root->left = insertElementBST(root->left, key);
    else if (key > root->value)
        root->right = insertElementBST(root->right, key);
}

node* deleteElementBST(node *root, int key)
{
    if (root == NULL)
        return root;

    if (key < root->value)
        root->left = deleteElementBST(root->left, key);
    else if (key > root->value)
        root->right = deleteElementBST(root->right, key);
    else if (key == root->value)
    {
        if (root->left == NULL)
        {
            node *p = root->right;
            free(root);
            return p;
        }
        else if (root->right == NULL)
        {
            node *p = root->left;
            free(root);
            return p;
        }

        node *p = minValueNode(root->right);
        root->value = p->value;
        root->right = deleteElementBST(root->right, p->value);
    }

    return root;
}

node* insertElementBBST(node *root, int key)
{
    if (root == NULL)
    {
        node *nju = (node*)malloc(sizeof(node));
        nju->left = nju->right = NULL;
        nju->value = key;
        return nju;
    }

    if (key < root->value)
        root->left = insertElementBBST(root->left, key);
    else if (key > root->value)
        root->right = insertElementBBST(root->right, key);

    int lf = height(root->left), rf = height(root->right);
    if (lf - rf < -1 || lf - rf > 1)
    {
        node *pl = root->left, *pr = root->right;
        if (lf - rf <= -2)
        {
            if (height(pr->left) - height(pr->right) <= 0)
                return leftRotation(root);
            else
            {
                root->right = rightRotation(root->right);
                return leftRotation(root);
            }
        }
        else if (lf - rf >= 2)
        {
            if (height(pl->left) - height(pl->right) >= 0)
                return rightRotation(root);
            else
            {
                root->left = leftRotation(root->left);
                return rightRotation(root);
            }
        }
    }

    return root;
}

node* deleteElementBBST(node *root, int key)
{
    if (root == NULL)
        return NULL;

    if (key < root->value)
        root->left = deleteElementBBST(root->left, key);
    else if (key > root->value)
        root->right = deleteElementBBST(root->right, key);
    else if (key == root->value)
    {
        if (root->left == NULL)
        {
            node *p = root->right;
            free(root);
            return p;
        }
        else if (root->right == NULL)
        {
            node *p = root->left;
            free(root);
            return p;
        }

        node *p = minValueNode(root->right);
        root->value = p->value;
        root->right = deleteElementBST(root->right, p->value);
    }

    int lf = height(root->left), rf = height(root->right);
    if (lf - rf < -1 || lf - rf > 1)
    {
        node *pl = root->left, *pr = root->right;
        if (lf - rf <= -2)
        {
            if (height(pr->left) - height(pr->right) <= 0)
                return leftRotation(root);
            else
            {
                root->right = rightRotation(root->right);
                return leftRotation(root);
            }
        }
        else if (lf - rf >= 2)
        {
            if (height(pl->left) - height(pl->right) >= 0)
                return rightRotation(root);
            else
            {
                root->left = leftRotation(root->left);
                return rightRotation(root);
            }
        }
    }

    return root;
}

void push(queue *q, tip element)
{
    if (q->front == 0)
    {
        q->front = q->rear = 1;
        q->arr[q->front] = element;
    }
    else
    {
        q->rear = q->rear%MAXN + 1;
        q->arr[q->rear] = element;
    }
}

tip pop(queue *q)
{
    if (q->front == 0)
    {
        printf("GRESKA: PRAZAN REDpop\n");
        exit(1);
    }

    tip ret = q->arr[q->front];
    if (q->front == q->rear)
        q->front = q->rear = 0;
    else
        q->front = q->front%MAXN + 1;
    return ret;
}

tip top(queue *q)
{
    if (q->front == 0)
    {
        printf("GRESKA: PRAZAN REDtop\n");
        exit(1);
    }

    return q->arr[q->front];
}

int empty(queue *q)
{
    if (q->front == 0)
        return 1;
    else
        return 0;
}

void push2(queue2 *q, tip2 element)
{
    if (q->front == 0)
    {
        q->front = q->rear = 1;
        q->arr[q->front] = element;
    }
    else
    {
        q->rear = q->rear%MAXN + 1;
        q->arr[q->rear] = element;
    }
}

tip2 pop2(queue2 *q)
{
    if (q->front == 0)
    {
        printf("GRESKA: PRAZAN REDpop\n");
        exit(1);
    }

    tip2 ret = q->arr[q->front];
    if (q->front == q->rear)
        q->front = q->rear = 0;
    else
        q->front = q->front%MAXN + 1;
    return ret;
}

tip2 top2(queue2 *q)
{
    if (q->front == 0)
    {
        printf("GRESKA: PRAZAN REDtop\n");
        exit(1);
    }

    return q->arr[q->front];
}

int empty2(queue2 *q)
{
    if (q->front == 0)
        return 1;
    else
        return 0;
}

node *minValueNode(node *root)
{
    while (root->left != NULL)
        root = root->left;
    return root;
}

node *maxValueNode(node *root)
{
    while (root->right != NULL)
        root = root->right;
    return root;
}

node* leftRotation(node *x)
{
    node *y = x->right;
    node *temp = y->left;
    y->left = x;
    x->right = temp;

    return y;
}

node* rightRotation(node *x)
{
    node *y = x->left;
    node *temp = y->right;
    y->right = x;
    x->left = temp;

    return y;
}

void inorder(node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", root->value);
        inorder(root->right);
    }
}

void writeInorder(node *root)
{
    printf("INORDER: ");
    inorder(root);
    printf("\n");
}

void levelOrder(node *root)
{
    queue q;
    q.front = q.rear = 0;
    push(&q, root);

    queue2 q2;
    q2.front = q2.rear = 0;
    push2(&q2, 0);

    while (!empty(&q))
    {
        node *cur = pop(&q);
        int height = pop2(&q2);
        printf("%d ", cur->value);

        if (cur->left != NULL)
        {
            push(&q, cur->left);
            push2(&q2, height + 1);
        }
        if (cur->right != NULL)
        {
            push(&q, cur->right);
            push2(&q2, height + 1);
        }

        if (!empty2(&q2) && top2(&q2) != height)
                printf("\n");
    }
    printf("\n");
}

void printAll(node *root)
{
    levelOrder(root);
}

void myPrintTree(node *root)
{
    if (root != NULL)
    {
        printf("%d ", root->value);
        if (root->left != NULL)
            printf("L: %d ", root->left->value);
        if (root->right != NULL)
            printf("R: %d", root->right->value);
        printf("\n");
        myPrintTree(root->left);
        myPrintTree(root->right);
    }
}

void preorder(node *root)
{
    if (root != NULL)
    {
        printf("%d ", root->value);
        preorder(root->left);
        preorder(root->right);
    }
}

void writePreorder(node *root)
{
    printf("PREORDER: ");
    preorder(root);
    printf("\n");
}

void postorder(node *root)
{
    if (root != NULL)
    {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->value);
    }
}

void writePostorder(node *root)
{
    printf("POSTORDER: ");
    postorder(root);
    printf("\n");
}

int height(node *root)
{
    if (root == NULL)
        return 0;
    int lf = 0, rf = 0;
    if (root->left != NULL)
        lf = height(root->left);
    if (root->right != NULL)
        rf = height(root->right);

    return max(lf, rf) + 1;
}

int checkGood(node *root, int *flag)
{
    if (root == NULL)
        return 0;

    int lf = 0, rf = 0;
    if (root->left != NULL)
        lf = checkGood(root->left, flag);
    if (root->right != NULL)
        rf = checkGood(root->right, flag);

    if (lf - rf < -1 || lf - rf > 1)
        *flag = 0;
    return max(lf, rf) + 1;
}

void isBalanced(node *root)
{
    int flag = 1;
    checkGood(root, &flag);

    if (!flag)
        printf("The tree is not balanced\n");
    else
        printf("The tree is balanced\n");
}

int max(int a, int b)
{
    return (a >= b) ? a : b;
}