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

Node* FindMin(TreeNode* root)
{
  
while(root->left != NULL)
root = root->left;

return root;

}

struct Node* Delete(TreeNode *root, int key)

{

if(data < root->key) root->left = Delete(root->left,key);
  
else if(key > root->key) root->right = Delete(root->right, key);

else {
  

TreeNode *temp = FindMin(root->right);

root->key = temp->key;

root->right = Delete(root->right, temp->data);
  
}

}

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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