I need to implement case 2 of this function, but I can\'t make it work correctly
ID: 3550180 • Letter: I
Question
I need to implement case 2 of this function, but I can't make it work correctly. What would a correct implementation be like?
/**
* Deletes a node containing 'key' in the tree rooted at 'root'.
*/
bool delete_node(Node*& root, KType key) {
Node* target;
Node* parent;
// find target node to delete
target = find(key, root);
if (!target) {
return false;
}
// find parent of target
parent = find_parent(root, target);
// case 1: target is a leaf
if (target->left == NULL && target->right == NULL) {
// set parent's child pointer
if (parent != NULL) {
if ( parent->left == target )
parent->left = NULL;
else
parent->right = NULL;
}
else
root = NULL;
// free target
delete target;
return true;
}
// case 2: target has two children
else if (target->left != NULL && target->right != NULL) {
/**
* THIS SECTION NEEDS TO BE IMPLEMENTED
*
* Add the missing lines here to make the function complete. (Hint: to
* remain a valid binary tree, you must replace 'target' with the
* largest key that is smaller than it.)
*/
return false; // return true when you're done.
}
// case 3: target has only left child
else if (target->left != NULL) {
// set parent's child pointer
if (parent != NULL) {
if ( parent->left == target )
parent->left = target->left;
else
parent->right = target->left;
}
else
root = target->left;
// free target
delete target;
return true;
}
// case 4: target has only right child
else {
// set parent's child pointer
if (parent != NULL) {
if (parent->left == target)
parent->left = target->right;
else
parent->right = target->right;
}
else
root = target->right;
// free target
delete target;
return true;
}
}
Explanation / Answer
void deleteNode(Tree **root)
{
Tree *prev=NULL,*toDelete=*root,*temp=NULL,*toSwap=NULL,*toSwapParent=NULL;
int flag=0,data=0;
printf("Input the data u want to delete: ");
scanf("%d", &data);
while(toDelete!=NULL && flag!=1)
{
if(toDelete->data == data)
{
flag=1;
break;
}
else if(toDelete->data > data)
{
prev=toDelete;
toDelete=toDelete->left;
}
else
{
prev=toDelete;
toDelete=toDelete->right;
}
}
if(flag==1)
{
if(toDelete->left == NULL && toDelete->right == NULL)
{
if(toDelete == *root)
*root = NULL;
else if(prev->left == toDelete)
prev->left = NULL;
else
prev->right = NULL;
}
else if(toDelete->left == NULL)
{
if(toDelete == *root)
*root = toDelete->right;
else if(prev->left == toDelete)
prev->left = toDelete->right;
else
prev->right = toDelete->right;
}
else if(toDelete->right == NULL)
{
if(toDelete == *root)
*root = toDelete->left;
else if(prev->left == toDelete)
prev->left = toDelete->left;
else
prev->right = toDelete->left;
}
else
{
toSwapParent = toDelete;
toSwap = toDelete->left;
while(toSwap->right != NULL)
{
toSwapParent = toSwap;
toSwap = toSwap->right;
}
toDelete->data = toSwap->data;
if(toSwapParent->right == toSwap)
toSwapParent->right = toSwap->left;
else
toSwapParent->left = toSwap->left;
temp = toDelete;
toDelete = toSwap;
toSwap = temp;
}
free(toDelete);
printf("Data Deleted !! ");
}
else
printf("Data not found !! ");
printf("Try again with another value. ");
return;
}