#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
    int data;
    struct Node*left;
    struct Node*right;
    int height;
} Node;
int height(Node*N){
    if(N == NULL)
      return 0;
    return N ->height;
}
Node*newNode(int data){
    Node*node=(Node*)malloc(sizeof(Node));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
    node->height=1;
    return node;
}
Node*rightRotate(Node*y){
    Node*x=y->left;
    Node*T2=x->right;
    x->right=y;
    y->left=T2;
    y->height=1+(height(y->left)>height(y->right)?height(y->left):height(y->right));
    x->height=1+(height(x->left)>height(x->right)?height(x->left):height(x->right));
    return x;
}
Node*leftRotate(Node*x){
    Node*y=x->right;
    Node*T2=y->left;
    y->left=x;
    x->right=T2;
    y->height=1+(height(x->left)>height(x->right)?height(x->left):height(x->right));
    y->height=1+(height(y->left)>height(y->right)?height(y->left):height(y->right));
    return y;
}
int getBalance(Node*N){
    if(N == NULL)
      return 0;
    return height(N->left)-height(N->right);
}
Node*insertNode(Node*node,int data){
    if(node == NULL)
      return newNode(data);
    if(node == NULL)
      node->left=insertNode(node->left,data);
    else
      node->left=insertNode(node->right,data);
    node->height=1+(height(node->left)>height(node->right)?height(node->left):height(node->right));
    int balance = getBalance(node);
    if(balance>1 && data < node->left->data)
      return rightRotate(node);
    if(balance <- 1 && data>node->right->data)
      return leftRotate(node);
}
if(balance<-1 && data<node->right->data){
    node->right=rightRotate(node->right);
    return leftRotate(node);
}
return node;
}
void inOrder(Node*root){
    if(root != NULL){
        inOrder(root->left);
        printf("%d",root->data);
        inOrder(root->right);
    }
}
int main(){
    int n;
    printf("Enter the number of nodes:");
    scanf("%d",&n);
    if(n<-10 || n>10){
        printf("Invalid input\n");
        return 0;
    }
    int*arr=(int*)malloc(n*sizeof(int));
    printf("Enter %d node values:",n);
    for(int i=0;i<n;i++)
      scanf("%d",&arr[i]);
    Node*root=NULL;
    for(int i=0;i<n;i++)
      root=insertNode(root,arr[i]);
    printf("In-order traversal of the AVL tree:");
    inOrder(root);
    printf("\n");
    return 0;
}