Write a C++ function to delete the given value from the binary search tree. The
ID: 3832826 • Letter: W
Question
Write a C++ function to delete the given value from the binary search tree. The function takes two arguments, tree node and value of the node to be deleted.
You only need to consider the case where the node has two children. The node should be replaced by the minimum node in its right subtree.
void deleteAndReplaceMinRight(TreeNode *root, int key); (just using this function) don't need other function
struct TreeNode {
int key;
TreeNode *left;
TreeNode *right;
TreeNode *parent;
};
For example:
If the node to be deleted is 30, delete it and replace it with the minimum of its right subtree. Final tree:
My code is like:
void deleteAndReplaceMinRight(TreeNode *root, int key)
{
TreeNode *temp = root-> right;
TreeNode *n = root;
while(n != NULL)
{
if(n->key > key)
{
n = n->left;
}
else if(n->key < key)
{
n = n->right;
}
else
{
if(n->key == key)
{
n = NULL;
while(temp->left != NULL)
{
temp = temp->left;
}
root->key = temp->key;
if(temp->right == NULL)
{
temp->parent->left = NULL;
}
else
{
temp->parent->left = temp->right;
}
}
}
}
}
Explanation / Answer
Answer -> the function to delete the given value from the binary search tree. This function takes two arguments, node and value of the node to be deleted.
struct node* deleteNode(node* root, int key)
{
if (root == NULL) return root;
// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < root->key)
root->left = deleteNode(root->left, key);
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (key > root->key)
root->right = deleteNode(root->right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
// node with two children: Get the inorder successor (smallest
// in the right subtree)
struct node* temp = minValueNode(root->right);
// Copy the inorder successor's content to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
/* this function is also used to return the node with minimum key value found in that tree. */
struct node * minValueNode(struct node* node)
{
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.