CodeChef: задание лаборатории колледжа, правила ротации / баланса AVL изменены

Question

Я даю ссылку на задание, объясняющее все.

https://www.codechef.com/problems/UCS616E1

Я попробовал все, насколько мне известно. Но безуспешно.

void link(node *&root){
    if(root!=NULL){
        if(root->right && root->left)    root->link=2;
        else if(root->left && root->right==NULL)  root->link=1;
        else if(root->right && root->left==NULL)  root->link=1;
        else if(root)   root->link=1;
        link(root->left);
        link(root->right);
    }
}
node *rt(node *root){
    node *temp = root->left;
    node *t2 = temp->right;
    temp->right = root;
    root->parent = temp;
    root->left = t2;
    t2->parent = root;
    return temp;
}
node *lf(node *root){
    node *t=root->right;
    node *t2=t->left;
    t->left=root;
    root->parent=t;
    root->right=t2;
    t2->parent=root;
    return t;
}
int treelink(node *N){
    return N->link;
}
node * balance(node *root){
    if(root==NULL)  return root;
    else if(treelink(root)==treelink(root->left)){
        root = rt(root);
    }
    else if(treelink(root)<=treelink(root->right->right)){
        root = lf(root);
        link(root);
    }
    root = balance(root->left);
    root = balance(root->right);
    return root;
}

Правильный вывод указан в предоставленной мной ссылке.