Write a C++ function to delete the given value from the binary search tree. The

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

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:

Explanation / Answer

struct TreeNode {
int key;
TreeNode *left;
TreeNode *right;
TreeNode *parent;
};

void deleteAndReplaceMinRight(TreeNode *root, int key)
{
    //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.
    TreeNode *temp = root->right;   //Start traversing the right subtree.
    while(temp->left != NULL)   //Keep moving to the left most position.
        temp = temp->left;
    root->key = temp->key   //Replacing the minimum node in the right subtree with the current node value.
    if(temp->right == NULL)   //If the minimum valued node in the right subtree has no children.
        temp->parent->left = NULL;
    else                   //If that left most node has a right child.
        temp->parent->left = temp->right;   //Attach that to the parent.
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.