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;
}```