AVL

#include <bits/stdc++.h>

class node{
public:
    int data;
    int height;
    node* left;
    node* right;

    node(int data) : data(data), height(1), left(nullptr), right(nullptr) {};

    int max(int a, int b){
        return ((a >= b) ? a : b);
    }

    int factor() {
        if (this == nullptr) return 0;
        int left_height = (left != nullptr) ? left->height : 0;
        int right_height = (right != nullptr) ? right->height : 0;
        return left_height - right_height;
    }

    node* right_rotation(){
        node* x = left;
        node* y = x->right;

        x->right = this;
        this->left = y;

        this->height = 1 + max((right ? right->height : 0), (left ? left->height : 0));
        x->height = 1 + max((x->right ? x->right->height : 0), (x->left ? x->left->height : 0));

        return x;
    }

    node* left_rotation(){
        node* x = right;
        node* y = x->left;

        x->left = this;
        this->right = y;

        this->height = 1 + max((right ? right->height : 0), (left ? left->height : 0));
        x->height = 1 + max((x->right ? x->right->height : 0), (x->left ? x->left->height : 0));

        return x;
    }

    node* insert(int key) {
        node*& dest = (key >= data) ? right : left;
        if (dest == nullptr) {
            dest = new node(key);
            this->height = 1 + max((right ? right->height : 0), (left ? left->height : 0));
            return this;
        } else if (key >= data) {
            right = right->insert(key);
        } else {
            left = left->insert(key);
        }

        this->height = 1 + max((right ? right->height : 0), (left ? left->height : 0));
        int balance_factor = this->factor();

        if (balance_factor > 1 && (left && key < left->data)) {
            return this->right_rotation();
        } else if (balance_factor < -1 && (right && key > right->data)) {
            return this->left_rotation();
        } else if (balance_factor > 1 && (left && key > left->data)) {
            left = left->left_rotation();
            return this->right_rotation();
        } else if (balance_factor < -1 && (right && key < right->data)) {
            right = right->right_rotation();
            return this->left_rotation();
        } else return this;
    }

    node* inorder_successor(){
        node* curr = this;
        while(curr->left){
            curr = curr->left;
        }
        return curr;
    }

    node* delete_node(int key){
        if (this == nullptr) return this;
        else if (key > data) right = right->delete_node(key);
        else if (key < data) left = left->delete_node(key);
        else {
            if (left == nullptr or right == nullptr){
                node* temp = (left) ? left : right;
                delete this;
                return temp;
                // if (temp == nullptr){
                //  temp = this;
                //  this = nullptr;
                // } else {
                //  *this = *temp;
                // }
            } else {
                node* temp = right->inorder_successor();
                data = temp->data;
                right = right->delete_node(key);
            }
        }

        if (this == nullptr) return this;

        this->height = 1 + max((right ? right->height : 0), (left ? left->height : 0));
        int balance_factor = this->factor();

        if (balance_factor > 1 && (left && key < left->data)) {
            return this->right_rotation();
        } else if (balance_factor < -1 && (right && key > right->data)) {
            return this->left_rotation();
        } else if (balance_factor > 1 && (left && key > left->data)) {
            left = left->left_rotation();
            return this->right_rotation();
        } else if (balance_factor < -1 && (right && key < right->data)) {
            right = right->right_rotation();
            return this->left_rotation();
        } else return this;
    }

    void inorder(){
        if (this == nullptr) return ;
        if (left != nullptr) left->inorder();
        std::cout << data << " ";
        if (right != nullptr) right->inorder();
        return ;
    }
    void level_order(){
        std::queue<node*> q;
        q.push(this);
        while(!q.empty()){
            node* curr = q.front();
            q.pop();
            if (curr != nullptr) {
                std::cout << curr->data << " " ;

                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
        }
        return ;
    }

};


int main(){
    node* root = new node(10);
    root = root->insert(5);
    root = root->insert(15);
    root = root->insert(12);
    root = root->insert(18);
    root = root->insert(20);
    root = root->insert(17);
    root = root->insert(19);
    root = root->insert(14);
    root = root->insert(13);
    root->inorder();
    std::cout << std::endl;
    root->level_order();

    return EXIT_SUCCESS;
}