1

I have a class of BST. I require a recursive function Rotate that takes the root of the BST as argument and returns a balanced BST.

Attached is the code that balances only one node, but it is not working for root node.

I want to make it recursive so it balances the whole tree but not the single node.

/* rotate */
Node* BST :: Rotate(Node* root)
{
    // gets the balance factor
    int balance = getBalance(root);

    // 4 cases for unbalanced BST

    // Left Left Case
    if (balance > 1 && root->data < root->left->data)
        return rightRotate(root);

    // Right Right Case
    if (balance < -1 && root->data > root->right->data)
        return leftRotate(root);

    // Left Right Case
    if (balance > 1 && root->data > root->left->data)
    {
        root->left =  leftRotate(root->left);
        return rightRotate(root);
    }

    // Right Left Case
    if (balance < -1 && root->data < root->right->data)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    /* return the (unchanged) node pointer */
    return root;
}
Toby Speight
  • 27,591
  • 48
  • 66
  • 103
Nidaa
  • 11
  • 2

0 Answers0