node* remove(int x, node* t)
{
node* temp;
// Element not found
if(t == NULL)
return NULL;
// Searching for element
else if(x < t->data)
t->left = remove(x, t->left);
else if(x > t->data)
t->right = remove(x, t->right);
// Element found
// With 2 children
else if(t->left && t->right)
{
temp = findMin(t->right);
t->data = temp->data;
t->right = remove(t->data, t->right);
}
// With one or zero child
else
{
temp = t;
if(t->left == NULL)
t = t->right;
else if(t->right == NULL)
t = t->left;
delete temp;
}
if(t == NULL)
return t;
t->height = max(height(t->left), height(t->right))+1;
// If node is unbalanced
// If left node is deleted, right case
if(height(t->left) - height(t->right) == 2)
{
// right right case
if(height(t->left->left) - height(t->left->right) == 1)
return singleLeftRotate(t);
// right left case
else
return doubleLeftRotate(t);
}
// If right node is deleted, left case
else if(height(t->right) - height(t->left) == 2)
{
// left left case
if(height(t->right->right) - height(t->right->left) == 1)
return singleRightRotate(t);
// left right case
else
return doubleRightRotate(t);
}
return t;
}