USE THE HEADER AND NOTHING ELSE void deleteAndReplaceLeftMin(TreeNode* root, int

Question

USE THE HEADER AND NOTHING ELSE void deleteAndReplaceLeftMin(TreeNode* root, int key)

Write a C++ function to delete the given value's right child from the binary search tree. The function takes two arguments, tree node and value of the node whose right child has to be deleted. Also replace the deleted node with minimum value from its left sub tree. The final tree will not be a valid BST. void deleteAndReplaceLeftMin(TreeNode *root, int key); structTreeNode {intkey; TreeNode "left; TreeNode "right; TreeNode "parent;} For example: If the key = 25, delete its right child which is 30. Then replace it with the minimum value in the left sub-tree (of 30) which is 27. The final tree is

Explanation / Answer

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

void deleteAndRelplaceLeftMin(ThreeNode* root, int key) {
   TreeNode *temp;
   while (root!=NULL) { //find node with value key
       if (key == root -> key)
           break;
       if (key < root -> key)
           root = root->left;
       if (key > root -> key)
           root = root->right;
   }

   if (root == NULL) {
        cout<<"Key not found ";
       return;
   }

   temp = root -> right; //temp is right subtree
  
   if (root == NULL) {
        cout<<"right child not found ";
       return;
   }  

   while (temp->left != NULL) //find leftmost child
       temp = temp->left;

   if (root->right == temp) {
        cout<<"left most child not found ";
       return;
   }

   temp->right = root->right>right; //copy child of node to be deleted
   temp->left = root->right->left;
   temp->parent->left = NULL; //remove link from parent
   temp->parent = root; //add new parent
   free(root->right); //free the removed node
   root-> right = temp; // replace the removed node
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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