Avl.cpp

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

struct Node
{
	int data, height;
	Node *left, *right;
	Node(int x)
	{
		data = x;
		height = 1;
		left = right = NULL;
	}
};

int height(Node *root){
    if(!root) return 0;
    int left=0,right=0;
    if(root->left) left=root->left->height;
    if(root->right) right=root->right->height;
    return root->height=max(left,right)+1;
}
int balance(Node *root){
    if(!root) return 0;
    int left=0,right=0;
    if(root->left) left=height(root->left);
    if(root->right) right=height(root->right);
    return left-right;
}
Node *left_rotate(Node *root){
    Node *tmp=root->right->left;
    root->right->left=root;
    root=root->right;
    root->left->right=tmp;
    height(root->right);
    height(root->left);
    height(root);
    return root;
}
Node *right_rotate(Node *root){
    Node *tmp=root->left->right;
    root->left->right=root;
    root=root->left;
    root->right->left=tmp;
    height(root->right);
    height(root->left);
    height(root);
    return root;
}
Node *rotation(Node *root){
    int bal=balance(root);
    if(bal>1 && balance(root->left)>=0){
        // right rotaion
        root=right_rotate(root);
    }
    else if(bal>1){
        // left right rotaion
        root->left=left_rotate(root->left);
        root=right_rotate(root);
    }
    else if(bal<-1 && balance(root->right)<=0){
        // left rotation
        root=left_rotate(root);
    }
    else if(bal<-1){
        // right left rotation
        root->right=right_rotate(root->right);
        root=left_rotate(root);
    }
    height(root);
    return root;
}

Node* insertToAVL(Node* root, int data)
{
    //Your code here
    if(!root) return new Node(data);
    if(data<root->data) root->left=insertToAVL(root->left,data);
    else if(data>root->data) root->right=insertToAVL(root->right,data);
    else return root;
    return rotation(root);
}
Node* deleteNode(Node* root, int data)
{
    if(!root) return NULL;
    if(root->data<data) root->right=deleteNode(root->right,data);
    else if(root->data>data) root->left=deleteNode(root->left,data);
    else {
        if(!root->right){
            Node *tmp=root;
            root=root->left;
            delete(tmp);
        }
        else if(!root->left){
            Node *tmp=root;
            root=root->right;
            delete(tmp);
        }
        else{
            Node *tmp=root->left;
            while(tmp->right) tmp=tmp->right;
            root->data=tmp->data;
            root->left=deleteNode(root->left,tmp->data);
        }
    }
    return rotation(root);
}
bool Search(Node *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(Node *root){
    if(root==NULL){
        cout<<"BST is empty";
        return -1;
    }
    else if (root->left==NULL)
    {
        return root->data;
    }
    return findMin(root->left);
}

void LevelOrder(Node *root){
    if(root==NULL){
        return;
    }
    queue<Node *>q;
    q.push(root);
    while(!q.empty()){
        Node * 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(Node *root){
    if(root==NULL){
        return;
    }
    Inorder(root->left);
    cout<<root->data<<" ";
    Inorder(root->right);
}

bool BstUtil(Node * 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(Node * root){
    return BstUtil(root,INT_MIN,INT_MAX);
}

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

    if(Search(root,-5)){
        cout<<"-5 Found\n";
    }
    else{
        cout<<"-5 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=deleteNode(root,11);
    root=deleteNode(root,10);
    root=deleteNode(root,2);
    root=deleteNode(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;
}