Write a C++ function to delete the given value\'s right child from the binary se

Question

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.

ONLYY USE THIS FUNCTION HEADER:

void deleteAndReplaceLeftMin(TreeNode *root, int key);

struct TreeNode

{

int key;

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

TreeNode* search(TreeNode *root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;
  
// Key is greater than root's key
if (root->key < key)
return search(root->right, key);

// Key is smaller than root's key
return search(root->left, key);
}

TreeNode* findMin(TreeNode *node)
{
TreNode* current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return current;
}

void deleteAndReplaceLeftMin(TreeNode *root, int key)
{
TreeNode *node = search(*root, key);
if (node->right == NULL)
{
return;
}
TreeNode *min = findMin(node->right);
if (min == NULL)
{
node->parent->right = node->right;
node->right->parent = node->parent;
delete node;
}
else
{
min->parent = node->parent;
node->parent->right = min;
min->right = node->right; // please note your algorithm do not handle case when min will have its own right child so am not trying to handle it.
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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