AVL TREE

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

class Node {

public:

    int data, height;

    Node *left, *right;

    Node(int val) {

        data = val;

        height = 1;

        left = right = NULL;

    }

};

int getHeight(Node* root) {

    if (!root) return 0;

    return root->height;

}

// -------- LEFT ROTATION --------

void leftRotate(Node*& root) {

    Node* right = root->right;

    Node* rightChild = right->left;

    right->left = root;

    root->right = rightChild;

    root->height = 1 + max(getHeight(root->left),

                            getHeight(root->right));

    right->height = 1 + max(getHeight(right->left),

                             getHeight(right->right));

    root = right;

}

// -------- RIGHT ROTATION --------

void rightRotate(Node*& root) {

    Node* left = root->left;

    Node* leftChild = left->right;

    left->right = root;

    root->left = leftChild;

    root->height = 1 + max(getHeight(root->left),

                            getHeight(root->right));

    left->height = 1 + max(getHeight(left->left),

                            getHeight(left->right));

    root = left;

}

int getBalance(Node* root) {

    if (!root) return 0;

    return getHeight(root->left) - getHeight(root->right);

}

// -------- PRINT TREE --------

void printTree(Node* root, int space = 0, int indent = 5) {

    if (!root) return;

    space += indent;

    printTree(root->right, space);

    cout << endl;

    for (int i = indent; i < space; i++)

        cout << " ";

    cout << root->data << "\n";

    printTree(root->left, space);

}

// -------- INSERT --------

void insert(Node*& root, int value) {

    if (!root) {

        root = new Node(value);

        return;

    }

    else{

        

    

    if (value < root->data)

        insert(root->left, value);

    else

        insert(root->right, value);

    root->height = 1 + max(getHeight(root->left),

                            getHeight(root->right));

    int balance = getBalance(root);

    // LL

    if (balance > 1 && value < root->left->data)

        rightRotate(root);

    // RR

    else if (balance < -1 && value > root->right->data)

        leftRotate(root);

    // LR

    else if (balance > 1 && value > root->left->data) {

        leftRotate(root->left);

        rightRotate(root);

    }

    // RL

    else if (balance < -1 && value < root->right->data) {

        rightRotate(root->right);

        leftRotate(root);

    }}

}

// -------- MAIN --------

int main() {

    Node* root = NULL;

    insert(root, 10);

    insert(root, 20);

    insert(root, 40);

    insert(root, 50);

    printTree(root);

    return 0;

}