AVL Tree Insertion

AVL Tree Insertion

AVL Tree Insertion

Given a root of the tree you need to perform N AVL tree insertion operations on it. You need to complete the method insertToAVL which takes 2 arguments the first is the root of the tree and the second is the value of the node to be inserted.The function should return the root of the modified tree.


The tree will be checked by driver code after each insertion. If after any insertion, the tree voilates the property of binary search tree or is not balanced, the driver code will print an error message informing about the voilation and print the inorder traversal of the tree at that moment. Further nodes will not be inserted to that tree. If instead, all insertions are done properly, while maintaining the properties of a balanced BST, no error message will be printed and the inorder traversal will be printed at the end, when all insertions are made.

Your Task:
Your task is to complete the function insertToAVL(). Return the root node of tree after inserting new node.

int hgt(Node* root)
{
    if(!root)return 0;
    // return 1+max(hgt(root->left),hgt(root->right));
    return root->height;
}

Node *rotateR(Node *root)
{
    Node *newroot=root->left;
    root->left=newroot->right;
    newroot->right=root;
    root->height=max(hgt(root->left),hgt(root->right))+1;
    newroot->height=max(hgt(newroot->left),hgt(newroot->right))+1;
  
    return newroot;
}

Node *rotateL(Node *root)
{
    Node *newroot=root->right;
    root->right=newroot->left;
    newroot->left=root;
     
    root->height=max(hgt(root->left),hgt(root->right))+1;
    newroot->height=max(hgt(newroot->left),hgt(newroot->right))+1;
      
    return newroot;
}

Node* insertToAVL(Node* root, int data)
{
    //Your code here/////
   
    if(!root)return new Node(data);
    if(root->data>data)
    {
        // root->height+=1;
        root->left=insertToAVL(root->left,data);
    }else if(root->data<data)
    {
        // root->height+=1;
        root->right=insertToAVL(root->right,data);
    }
    int bal=hgt(root->left)-hgt(root->right);
   
//you can use either this one or below this one both same work done
    // if(bal>1&&root->left->data>data)
    // {
    //     return rotateR(root);
       
    // }
    // if(bal>1&&root->left->data<data)
    // {
    //     root->left=rotateL(root->left);
    //         return rotateR(root);
    // }
    // if(bal<-1&&root->right->data<data)
    // {
    //     return rotateL(root);
    // }
    //  if(bal<-1&&root->right->data>data)
    // {
    //     root->right=rotateR(root->right);
    //     return rotateL(root);
    // }
    if(bal>1)
    {
        if(hgt(root->left->left)>=hgt(root->left->right))
        {
            return rotateR(root);
        }else{
            root->left=rotateL(root->left);
            return rotateR(root);
        }
    }
    if(bal<-1)
    {
         if(hgt(root->right->left)<=hgt(root->right->right))
        {
            return rotateL(root);
        }else{
            root->right=rotateR(root->right);
            return rotateL(root);
        }
    }
    root->height=max(hgt(root->left),hgt(root->right))+1;
    return root;
}