HackerRank Self Balancing Tree problem solution

In this tutorial, we are going to solve or make a solution to the Self Balancing Tree problem. so here we have given a pointer to the root node of an AVL tree. and we need to insert a value into the tree and perform the necessary rotation to balance a tree.

Problem solution in Java Programming.

static Node insert(Node root,int val) {
       if(root == null) {
           root = new Node();
           root.val = val;
           root.ht = setHeight(root);
           return root;
       }
       if(val <= root.val) {
           root.left = insert(root.left, val);
       }
       else if (val > root.val) {
           root.right = insert(root.right, val);
       }
       int balance = height(root.left) - height(root.right);
       
       if(balance > 1) {
           if(height(root.left.left) >= height(root.left.right)) {
               root = rightRotation(root);
           }
           else {
               root.left = leftRotation(root.left);
               root = rightRotation(root);
           }
       }
       else if(balance < -1) {
           if(height(root.right.right) >= height(root.right.left)) {
               root = leftRotation(root);
           }
           else {
               root.right = rightRotation(root.right);
               root = leftRotation(root);
           }
       }
       else {
           root.ht = setHeight(root);
       }
       return root;
   }

   private static Node rightRotation(Node root) {
       Node newRoot = root.left;
       root.left = newRoot.right;
       newRoot.right = root;
       root.ht = setHeight(root);
       newRoot.ht = setHeight(newRoot);
       return newRoot;
   }

   private static Node leftRotation(Node root) {
       Node newRoot = root.right;
       root.right = newRoot.left;
       newRoot.left = root;
       root.ht = setHeight(root);
       newRoot.ht = setHeight(newRoot);
       return newRoot;
   }

   private static int height(Node root) {
       if(root == null)
           return -1;
       else 
           return root.ht;
   }

   private static int setHeight(Node root) {
       if(root == null) {
           return -1;
       } 
       else {
           return 1 + Math.max(height(root.left), height(root.right));
       }
   }

Problem solution in C++ programming.

int height(node * root)
{
  if (root)
    return root->ht;
  else
    return -1;
}

void rotateRight(node * & root)
{
    node* temp = root->left;
    root->left = root->left->right;
    temp->right = root;
    root->ht = 1 + ((height(root->right) > height(root->left)) ? height(root->right) : height(root->left));
    temp->ht = 1 + ((height(temp->right) > height(temp->left)) ? height(temp->right) : height(temp->left));
    root = temp;
}

void rotateLeft(node * & root)
{
    node* temp = root->right;
    root->right = root->right->left;
    temp->left = root;
    root->ht = 1 + ((height(root->right) > height(root->left)) ? height(root->right) : height(root->left));
    temp->ht = 1 + ((height(temp->right) > height(temp->left)) ? height(temp->right) : height(temp->left));
    root = temp;
}

void rotateLeftRight(node * & root)
{
    rotateLeft(root->left);
    rotateRight(root);
}

void rotateRightLeft(node * & root)
{
    rotateRight(root->right);
    rotateLeft(root);
}
void insert1(node * & root, int val)
{
    if(root == NULL)
   {
       root = new node();
       root->val = val;
       root->left = NULL;
       root->right = NULL;
       root->ht = 0;
   }
   else if(root->val > val)
   {
       insert1(root->left, val);
       int balance = height(root->right) - height(root->left);
       int leftbalance = height(root->left->right) - height(root->left->left);
       if(balance == -2)
       {
           if(leftbalance == -1)
           {
               rotateRight(root);
           }
           if(leftbalance == +1)
           {
               rotateLeftRight(root);
           }
       }
   }

   else if(root->val < val)
   {
       insert1(root->right, val);
       int balance = height(root->right) - height(root->left);
       int rightbalance = height(root->right->right) - height(root->right->left);
       if(balance == 2)
       {
           if(rightbalance == 1)
           {
               rotateLeft(root);
           }
           if(rightbalance == -1)
           {
               rotateRightLeft(root);
           }
       }
   }
    root->ht = 1 + ((height(root->right) > height(root->left)) ? height(root->right) : height(root->left));
}

node * insert(node * root,int val)
{
   insert1(root, val);
   return root;
}