AVLTree Insert

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

node* newNode(int val)
{
    node* n = new node;
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    n->ht = 0;
    return n;
}
int height(node *root)
{
    if(root==NULL)
        return -1;
    return root->ht;
}
int getBalance(node* root)
{
    if(root==NULL)
        return 0;
    int l = height(root->left);
    int r = height(root->right);
    //cout << root->val << " " << l << " " << r << endl;
    return l-r;
}
node* leftRotate(node* x)
{
    node* y = x->right;
    node* T2 = y->left;

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

    x->ht = 1+max(height(x->left),height(x->right));
    y->ht = 1+max(height(y->left),height(y->right));

    return y;
}
node* rightRotate(node* y)
{
    node* x = y->left;
    node* T2 = x->right;

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

    y->ht = 1+max(height(y->left),height(y->right));
    x->ht = 1+max(height(x->left),height(x->right));

    return x;
}
node * insert(node * root,int val)
{
    if(root == NULL)
    {
        return newNode(val);
    }
    if(val < root->val)
    {
        root->left = insert(root->left,val);
    }
    else if(val > root->val)
    {
        root->right = insert(root->right,val);
    }
    else
        return root;
    root->ht = 1+max(height(root->left),height(root->right));
    int balance = getBalance(root);
    if(balance > 1  && val < root->left->val)
    {
        return rightRotate(root);
    }
    else if(balance < -1 && val > root->right->val)
    {
        return leftRotate(root);
    }
    else if(balance > 1 && val > root->left->val)
    {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    else if(balance < -1 && val < root->right->val)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}