BST balance

[bamboojack]

I am trying to balance a tree by height (an AVI tree).

When I give it a tree like this:
Pre Order Traversal:
15 8 5 3 6 12 18

It works fine, but when I test it using this tree:
Pre Order Traversal:
10 5 15 12 20 19 25 23 30 29 35
and I get:
Pre Order Traversal:
15 10 5 12 20 19 25 23 30 29 35

where am I going wrong?

int height(TreeNode *node){
    if(node == NULL){
        return 0;
    }
    else{
        return (max(height(node->leftChild), height(node->rightChild)) + 1);
    }
}

int diff(TreeNode *temp){
    int l_height = height (temp->leftChild);
    int r_height = height (temp->rightChild);
    int b_factor= l_height - r_height;
    return b_factor;
}

TreeNode *rr_rotation(TreeNode *parent){
    TreeNode *temp;
    temp = parent->rightChild;
    parent->rightChild = temp->leftChild;
    temp->leftChild = parent;
    return temp;
}

TreeNode *ll_rotation(TreeNode *parent){
    TreeNode *temp;
    temp = parent->leftChild;
    parent->leftChild = temp->rightChild;
    temp->rightChild = parent;
    return temp;
}

TreeNode *lr_rotation(TreeNode *parent){
    TreeNode *temp;
    temp = parent->leftChild;
    parent->leftChild = rr_rotation(temp);
    return ll_rotation(parent);
}

TreeNode *rl_rotation(TreeNode *parent)
{
    TreeNode *temp;
    temp = parent->rightChild;
    parent->rightChild = ll_rotation(temp);
    return rr_rotation(parent);
}

TreeNode * CheckHeightAndRotate(TreeNode *root){.
    TreeNode *temp = root;
    int bal_factor = diff (temp);
    if (bal_factor > 1){
        if (diff (temp->leftChild) > 0){
            temp = ll_rotation (temp);
        }
        else{
            temp = lr_rotation (temp);
        }
    }
    else if (bal_factor < -1){
        if (diff (temp->rightChild) > 0){
            temp = rl_rotation (temp);
        }
        else{
            temp = rr_rotation (temp);
        }
    }
    return temp;
}

[Lord Razgriz]

In your CheckHeightAndRotate, you need to add a while loop right after implementing bal_factor to check if the bal_factor is still > 1 or < -1. Then put bal_factor = diff (temp); as the first thing in the while loop. This may seem strange, but this will allow the function to properly fix trees that are heavily lopsided to one side or another by repeatedly checking if the bal_factor is still to big or small.