Write a C++ function to delete the given value from the binary search tree. The
ID: 3676885 • 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. Also replace the node to be deleted with maximum value from left sub tree when the node has two children.
void deleteAndReplaceMinRight(TreeNode *root, int key);
struct TreeNode
{
int key;
TreeNode *left;
TreeNode *right;
TreeNode *parent;
};
I am getting a runtime error Here is my code:
void deleteAndReplaceMinRight(TreeNode *root, int key){
TreeNode *tmp = root;
bool run = true;
while (tmp != NULL && run == true) {
if (tmp->key == key) {
run = false;
break;
}
if (key < tmp->key) {
if(tmp->left == NULL) {
return;
}
tmp = tmp->left;
}
else {
if (tmp->right == NULL) {
return;
}
tmp = tmp->right;
}
}
TreeNode *maximum = tmp->left;
while (maximum->right != NULL) {
maximum = maximum->right;
}
bool leftchild = false;
if (maximum->left != NULL) {
maximum->parent->right =maximum->left;
leftchild = true;
}
if (tmp->left != NULL && tmp->right != NULL) {
tmp ->parent->left = maximum;
if (leftchild == false)
maximum->parent->right = NULL;
maximum->parent = tmp->parent;
maximum->left = tmp->left;
maximum->right = tmp->right;
free (tmp);
}
if (tmp->left != NULL && tmp->right == NULL) {
if (tmp->parent->left == tmp) {
tmp->parent->left = tmp ->left;
}
else tmp->parent->right = tmp->left;
free (tmp);
}
else if(tmp->right != NULL && tmp->left != NULL){ //replacing
TreeNode *x = tmp->right;
while (x->left != NULL){
x = x->left;
}
if(tmp != root){
if(tmp->parent->left == tmp){
if(x == tmp->right){
tmp->parent->left = x;
x->parent = tmp->parent;
x->left = tmp->left;
}
else{
x->parent->left = x->right;
x->parent = tmp->parent;
x->right->parent = x->parent;
tmp->parent->left = x;
x->left = tmp->left;
x->right = tmp->right;
tmp->right->parent = x;
tmp->left->parent = x;
}
}
else{
if(x == tmp->right){
tmp->parent->right = x;
x->parent = tmp->parent;
}
else{
x->parent->left = x->right;
x->parent = tmp->parent;
x->right->parent = x->parent;
tmp->parent->right = x;
x->left= tmp->left;
x->right = tmp->right;
tmp->right->parent = x;
tmp->left->parent = x;
}
}
delete tmp;
}
}
}
Explanation / Answer
Hi please try this code for best result and replace the node to be deleted with maximum value from left sub tree when the node has two children. correction in bold characters
void deleteAndReplaceMaxRight(TreeNode *root, int key){
TreeNode *tmp = root;
bool run = true;
while (tmp != NULL && run == true) {
if (tmp->key == key) {
run = false;
break;
}
if (key < tmp->key) {
if(tmp->left == NULL) {
return;
}
tmp = tmp->left;
}
else {
if (tmp->right == NULL) {
return;
}
tmp = tmp->right;
}
}
TreeNode *maximum = tmp->left;
while (maximum->right != NULL)
{
maximum = maximum->right;
}
bool leftchild = false;
if (maximum->left != NULL)
{
maximum->parent->right =maximum->left;
leftchild = true;
}
if (tmp->left != NULL && tmp->right != NULL)
{
tmp ->parent->left = maximum;
if (leftchild == false)
maximum->parent->right = NULL;
maximum->parent = tmp->parent;
maximum->left = tmp->left;
maximum->right = tmp->right;
free (tmp);
}
if (tmp->left != NULL && tmp->right == NULL)
{
tmp ->parent->left = maximum;
if (leftchild == false)
maximum->parent->right = NULL;
maximum->parent = tmp->parent;
maximum->left = tmp->left;
maximum->right = null;
free (tmp);
}
else if(tmp->right != NULL && tmp->left == NULL)
{ //replacing
TreeNode *x = tmp->right;
while (x->left != NULL)
{
x = x->left;
}
if(tmp != root)
{
if(tmp->parent->left == tmp)
{
if(x == tmp->right)
{
tmp->parent->left = x;
x->parent = tmp->parent;
x->left = tmp->left;
}
else
{
x->parent->left = x->right;
x->parent = tmp->parent;
x->right->parent = x->parent;
tmp->parent->left = x;
x->left = tmp->left;
x->right = tmp->right;
tmp->right->parent = x;
tmp->left->parent = x;
}
}
else
{
if(x == tmp->right)
{
tmp->parent->right = x;
x->parent = tmp->parent;
}
else
{
x->parent->left = x->right;
x->parent = tmp->parent;
x->right->parent = x->parent;
tmp->parent->right = x;
x->left= tmp->left;
x->right = tmp->right;
tmp->right->parent = x;
tmp->left->parent = x;
}
}
delete tmp;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.