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

/* ---------- NODE DEFINITION ---------- */
typedef struct node {
    int key;
    int height;
    struct node *left;
    struct node *right;
} node;

/* ---------- UTILITY FUNCTIONS ---------- */
int max(int a, int b) {
    return (a > b) ? a : b;
}

int height(node *n) {
    return (n == NULL) ? 0 : n->height;
}

node* createNode(int key) {
    node *n = (node*)malloc(sizeof(node));
    n->key = key;
    n->left = NULL;
    n->right = NULL;
    n->height = 1;   // leaf node
    return n;
}

/* ---------- ROTATIONS ---------- */
node* rightRotate(node *y) {
    node *x = y->left;
    node *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

node* leftRotate(node *x) {
    node *y = x->right;
    node *T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

int getBalance(node *n) {
    return (n == NULL) ? 0 : height(n->left) - height(n->right);
}

/* ---------- AVL INSERT ---------- */
node* insert(node *root, int key) {
    if (root == NULL)
        return createNode(key);

    if (key < root->key)
        root->left = insert(root->left, key);
    else if (key > root->key)
        root->right = insert(root->right, key);
    else
        return root;   // no duplicates

    root->height = 1 + max(height(root->left), height(root->right));
    int balance = getBalance(root);

    /* LL case */
    if (balance > 1 && key < root->left->key)
        return rightRotate(root);

    /* RR case */
    if (balance < -1 && key > root->right->key)
        return leftRotate(root);

    /* LR case */
    if (balance > 1 && key > root->left->key) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    /* RL case */
    if (balance < -1 && key < root->right->key) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

/* ---------- TREE PRINT (YOUR FORMAT) ---------- */
void printtree(node *root, int space, int n)
{
    int i;

    if (root == NULL)
        return;

    space += n;

    printtree(root->right, space, n);

    printf("\n");
    for (i = n; i < space; i++)
        printf(" ");

    printf("(%d)", root->key);

    printtree(root->left, space, n);
}

/* ---------- MAIN (AS REQUESTED) ---------- */
int main()
{
    node *root = NULL;
    int n, i, key;

    printf("enter the number of nodes\n");
    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        printf("enter the key\n");
        scanf("%d", &key);
        root = insert(root, key);
    }

    printf("\nAVL Tree:\n");
    printtree(root, 0, n);

    return 0;
}