#include <iostream>

using namespace std;

struct Node {
    int data;
    unsigned char height;
    Node *Left, *Right;
    Node(int data) {
        this->data = data;
        Left = Right = nullptr;
        height = 1;
    }
} *Root;

unsigned char get_height(Node* temp) {
    return temp ? temp->height : 0;
}

int b_factor(Node* temp) {
    return get_height(temp->Right) - get_height(temp->Left);
}

void fix_height(Node* temp) {
    unsigned char h_l = get_height(temp->Left);
    unsigned char h_r = get_height(temp->Right);
    temp->height = (h_l > h_r ? h_l : h_r) + 1;
}

Node* rotate_right(Node* temp) {
    Node *x = temp->Left;
    temp->Left = x->Right;
    x->Right = temp;
    fix_height(temp);
    fix_height(x);
    return x;
}

Node* rotate_left(Node* temp) {
    Node *x = temp->Right;
    temp->Right = x->Left;
    x->Left = temp;
    fix_height(temp);
    fix_height(x);
    return x;
}

Node* balance(Node* temp) {
    fix_height(temp);
    if(b_factor(temp) == 2) {
        if(b_factor(temp->Right) < 0) {
            temp->Right = rotate_right(temp->Right);
            return rotate_left(temp);
        }
    } else if(b_factor(temp) == -2) {
        if(b_factor(temp->Left) < 0) {
            temp->Left = rotate_right(temp->Left);
            return rotate_right(temp);
        }
    }
    return temp;
}

Node* insert(Node* temp, int key) {
    if(!temp) {
        return new Node(key);
    }
    if(key > temp->data) {
        temp->Right = insert(temp->Right, key);
    } else {
        temp->Left = insert(temp->Left, key);
    }
    return balance(temp);
}

Node* find_min(Node* temp) {
    return temp->Left ? find_min(temp->Left) : temp;
}

Node* remove_min(Node* temp) {
    if(temp->Left == nullptr) {
        return temp->Right;
    }
    temp->Left = remove_min(temp->Left);
    return balance(temp);
}

Node* remove(Node* temp, int key) {
    if(!temp) {
        return 0;
    }
    if(key > temp->data) {
        temp->Right = remove(temp->Right, key);
    } else if(key < temp->data){
        temp->Left = remove(temp->Left, key);
    } else {
        Node* l = temp->Left;
        Node* r = temp->Right;
        delete temp;
        if(!r) {
            return l;
        }
        Node* _min = find_min(r);
        _min->Right = remove_min(r);
        _min->Left = l;
        return balance(_min);
    }
    return balance(temp);
}


void preOrderTravers(Node* root) {
    if (root) {
        printf("%d ", root->data);
        preOrderTravers(root->Left);
        preOrderTravers(root->Right);
    }
}
void postOrderTravers(Node* root) {
    if (root) {
        postOrderTravers(root->Left);
        postOrderTravers(root->Right);
        printf("%d ", root->data);
    }
}


void show(Node* temp, int dep) {
    if(temp) {
        show(temp->Right, dep + 1);
        for(int i = 0; i < dep; ++i) {
            cout << ' ';
        }
        cout << temp->data << endl;
        show(temp->Left, dep + 1);
    }
}

int main() {
    Root = insert(Root, 10);
    Root = insert(Root, 20);
    Root = insert(Root, 50);
    Root = insert(Root, 5);

    //show(Root, 0);

    //Root = remove(Root, 10);

    //show(Root, 0);
    preOrderTravers(Root);
    cout << endl;
    postOrderTravers(Root);
}