//    AVL Implemented
#include<bits/stdc++.h>
using namespace std;

struct BstNode{
    int data;
    BstNode *left,*right;
    int height;
    BstNode(int d)
    {
        data=d;
        left=NULL;
        right=NULL;
        height=0;
    }
};

int height(BstNode *N){
    if(N==NULL){
        return -1;
    }
    return N->height;
}

BstNode * L_rotate(BstNode *root){
    BstNode *l=root->left;
    BstNode *temp=l->right;
    l->right=root;
    root->left=temp;
    // Update Heights
    root->height=max(height(root->left),height(root->right))+1;
    l->height=max(height(l->left),height(l->right))+1;
    return l;
}

BstNode * R_rotate(BstNode *root){
    BstNode *r=root->right;
    BstNode *temp=r->left;
    r->left=root;
    root->right=temp;
    // Update Heights
    root->height=max(height(root->left),height(root->right))+1;
    r->height=max(height(r->left),height(r->right))+1;
    return r;
}

int getBalance(BstNode *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

BstNode * Insert(BstNode *root,int value){
    BstNode *temp=new BstNode(value);
    if(root==NULL){
        root=temp;
    }
    else if(value <= root->data){
        root->left=Insert(root->left,value);
    }
    else
    {
        root->right=Insert(root->right,value);
    }
    root->height=max(height(root->left),height(root->right))+1;
    // AVL Implementation
    // check balance or not
    int balance=getBalance(root);
    // if unbalanced
    // Left case
    if(balance>1 && value < root->left->data){
        return L_rotate(root);
    }
    // Right case
    if(balance<-1 && value > root->right->data){
        return R_rotate(root);
    }
    // Right Left case
    if(balance>1 && value > root->left->data){
        root->left = R_rotate(root->left);
        return L_rotate(root);
    }
    // Left Right case
    if(balance<-1 && value < root->right->data){
        root->right = L_rotate(root->right);
        return R_rotate(root);
    }
    return root;
}

bool Search(BstNode *root,int value){
    if(root==NULL){
        return false;
    }
    else if(root->data==value){
        return true;
    }
    else if(root->data < value)
    {
        return Search(root->left,value);
    }
    else
    {
        return Search(root->right,value);
    }
}

int findMin(BstNode *root){
    if(root==NULL){
        cout<<"BST is empty";
        return -1;
    }
    else if (root->left==NULL)
    {
        return root->data;
    }
    return findMin(root->left);
}

void LevelOrder(BstNode *root){
    if(root==NULL){
        return;
    }
    queue<BstNode *>q;
    q.push(root);
    while(!q.empty()){
        BstNode * curr=q.front();
        cout<<curr->data<<" ";
        if(curr->left!=NULL){
            q.push(curr->left);
        }
        if(curr->right!=NULL){
            q.push(curr->right);
        }
        q.pop();
    }
}

void Inorder(BstNode *root){
    if(root==NULL){
        return;
    }
    Inorder(root->left);
    cout<<root->data<<" ";
    Inorder(root->right);
}

bool BstUtil(BstNode * root,int min,int max){
    if(root==NULL){
        return true;
    }
    if((root->data <= max)&&(root->data > min) &&
        BstUtil(root->left,min,root->data) &&
         BstUtil(root->right,root->data,max)){
            return true;
         }
    else{
    return false;
    }
}

bool isBst(BstNode * root){
    return BstUtil(root,INT_MIN,INT_MAX);
}

BstNode * Delete(BstNode *root,int value){
    if(root==NULL){
        return root;
    }
    else if(value < root->data){
        root->left=Delete(root->left,value);
    }
    else if(value > root->data){
        root->right=Delete(root->right,value);
    }
    else         // I find you & going to delete you
    {
        // case 1: no child
        if(root->left==NULL && root->right==NULL){
            delete root;
            root=NULL;
            return root;
        }
        // case 2: only 1 child
        else if(root->left==NULL){
            BstNode *temp=root;
            root=root->right;
            delete temp;
        }
        else if(root->right==NULL){
            BstNode *temp=root;
            root=root->left;
            delete temp;
        }
        // case 3: 2 children
        else{
            int min=findMin(root->right);
            root->data=min;
            root->right=Delete(root->right,min);
        }
    }
    root->height=max(height(root->left),height(root->right))+1;
    // AVL Implementation
    // check balance or not
    int balance=getBalance(root);
    // if unbalanced
    // Left case
    if(balance>1 && value < root->left->data){
        return L_rotate(root);
    }
    // Right case
    if(balance<-1 && value > root->right->data){
        return R_rotate(root);
    }
    // Right Left case
    if(balance>1 && value > root->left->data){
        root->left = R_rotate(root->left);
        return L_rotate(root);
    }
    // Left Right case
    if(balance<-1 && value < root->right->data){
        root->right = L_rotate(root->right);
        return R_rotate(root);
    }
    return root;
}

// void storeBst(BstNode *root,vector<BstNode *> &v){
//     if(root==NULL){
//         return;
//     }
//     storeBst(root->left,v);
//     v.push_back(root);
//     storeBst(root->right,v);
// }

// BstNode * buildtree(vector<BstNode *>v,int start,int end){
//     if(start>end){
//         return NULL;
//     }
//     int mid=(start+end)/2;
//     BstNode *root=v[mid];
//     root->left=buildtree(v,start,mid-1);
//     root->right=buildtree(v,mid+1,end);

//     return root;
// }

// BstNode * balance(BstNode *root){
//     vector<BstNode *>v;
//     storeBst(root,v);

//     int n=v.size();
//     return buildtree(v,0,n-1);
// }

// Before AVL Tree Implementation
//             15
//        10        17
//      1    14    16  18
//       2  12
//         11

int main(){
    BstNode *root=NULL;
    root=Insert(root,15);
    root=Insert(root,10);
    root=Insert(root,14);
    root=Insert(root,11);
    root=Insert(root,12);
    root=Insert(root,1);
    root=Insert(root,2);
    root=Insert(root,17);
    root=Insert(root,16);
    root=Insert(root,18);

    if(Search(root,-5)){
        cout<<"Found\n";
    }
    else{
        cout<<"Not Found\n";
    }
    cout<<"Min "<<findMin(root);
    cout<<"\nHeight "<<height(root);
    cout<<"\nLevelOrder: ";
    LevelOrder(root);
    cout<<"\nInorder: ";
    Inorder(root);
    cout<<"\nCheck Bst or not? \n";
    if(isBst(root)){
        cout<<"\tYes,it is bst\n";
    }
    else{
        cout<<"\tNo,it is not a bst";
    }
    cout<<"DELETE 10,11,2,18: ";
    root=Delete(root,11);
    root=Delete(root,10);
    root=Delete(root,2);
    root=Delete(root,18);
    LevelOrder(root);
    cout<<"\nHeight "<<height(root);
    cout<<"\nCheck Bst or not? \n";
    if(isBst(root)){
        cout<<"\tYes,it is bst\n";
    }
    else{
        cout<<"\tNo,it is not a bst";
    }
    return 0;
}