Description

Submission

/* Node is defined as :
typedef struct node
{
    int val;
    struct node* left;
    struct node* right;
    int ht;
} node; */

int calculateHeight(node* root)
{
    if(root == NULL) return -1;
    int lHeight = -1;
    int rHeight = -1;
    if(root->left) lHeight = root->left->ht;
    if(root->right) rHeight = root->right->ht;
    root->ht = max(lHeight, rHeight) + 1;
    return root->ht;
}

int getBF(node* root)
{
    return calculateHeight(root->left) - calculateHeight(root->right);
}

node * insert(node * root,int val)
{
    if(root == NULL) {
        root = new node;
        root->val = val;
        root->right = NULL;
        root->left = NULL;
        root->ht = 0;
        return root;
    }

    if(val < root->val) {
        if(root->left) root->left = insert(root->left, val);
        else {
            root->left = new node;
            root->left->val = val;
            root->left->left = NULL;
            root->left->right = NULL;
            root->left->ht = 0;
        }

    }
    if(val > root->val) {
        if(root->right) root->right = insert(root->right, val);
        else {
            root->right = new node;
            root->right->val = val;
            root->right->left = NULL;
            root->right->right = NULL;
            root->right->ht = 0;
        }
    }

    if(getBF(root) == 2) {
        if(getBF(root->left) == -1) {
            node* tmp = root->left;
            root->left = tmp->right;
            tmp->right = root->left->left;
            root->left->left = tmp;
            calculateHeight(root->left->left);
            calculateHeight(root->left);
            calculateHeight(root);
        }
        if(getBF(root->left) >= 0) {
            node* tmp = root;
            root = tmp->left;
            tmp->left = root->right;
            root->right = tmp;
            calculateHeight(root->left);
            calculateHeight(root->right);
            calculateHeight(root);
        }
    }

    if(getBF(root) == -2) {
        if(getBF(root->right) == 1) {
            node* tmp = root->right;
            root->right = tmp->left;
            tmp->left = root->right->right;
            root->right->right = tmp;
            calculateHeight(root->right->right);
            calculateHeight(root->right);
            calculateHeight(root);
        }

        if(getBF(root->right)<= 0) {
            node* tmp = root;
            root = tmp->right;
            tmp->right = root->left;
            root->left = tmp;
            calculateHeight(root->left);
            calculateHeight(root->right);
            calculateHeight(root);
        }
    }

    return root;
}