/*AVL self-balancing trees: Insertion of a node
- This took me so much time, so I had to post this.
*/

/* Assumption:
1. Null node have a height of -1
2. Leaf node have a height of 0
*/

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

int getHeight(node* n){
    if(n==NULL) return -1;
    return n->ht;
}

int getBalance(node* r){
    if(r==NULL) return -1;
    return getHeight(r->left) - getHeight(r->right);
}

node* leftRotate(node* n){
    node* right = n->right;
    node* tree = right->left;

    // rotation
    right->left = n;
    n->right = tree;

    // height update
    n->ht = max(getHeight(n->left), getHeight(n->right)) + 1;
    right->ht = max(getHeight(right->left), getHeight(right->right)) + 1;

    return right;
}

node* rightRotate(node* n){
    node* left = n->left;
    node* tree = left->right;

    // rotation
    left->right = n;
    n->left = tree;

    // height updates
    n->ht = max(getHeight(n->left), getHeight(n->right)) + 1;
    left->ht = max(getHeight(left->left), getHeight(left->right)) + 1;

    return left;
}

node* insert(node * root, int val){
    // insertion at leaf
    if(root == NULL){node* n = new node(); n->val = val; n->ht = 0; return n;}

    if(val< root->val){
        root->left = insert(root->left, val);
    }else if(val > root->val){
        root->right = insert(root->right, val);
    }else{
        // this case not allowed in AVL-trees (no duplicates)
        return root;
    }

    root->ht = 1 + max(getHeight(root->left), getHeight(root->right));
    int bal = getBalance(root);

    // Cases
    // left left case
    if(bal > 1 && val < root->left->val){
        return rightRotate(root);
    }
    // right right case
    if(bal < -1 && val > root->right->val){
        return leftRotate(root);
    }
    // left right case
    if(bal > 1 && val > root->left->val){
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    //right left case
    if(bal < -1 && val < root->right->val){
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

/* It works for me. If it doesn't work for you: Drop me a mail by raising an issue: ankit03june AT gmail DOT com*/