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;
}