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. Also replace the node to be deleted with the minimum of its right subtree when the node has two children.

Please use the same struct

struct TreeNode

{

int key;

TreeNode *left;

TreeNode *right;

TreeNode *parent;

};

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 the minimum of its right subtree when the node has two children. void deleteAndReplaceMinRight TreeNode "root, int key): struct TreeNode int key TreeNode·left; TreeNode "right TreeNode 'parent For example: 25 15 30 28 35 27 29 33 70 25 15 33 28 35 27 29 70

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

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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