Write a C++ function to delete the given value from the binary search tree. The

ID: 3677328 • 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.

The struct ->

struct TreeNode

{

int key;

TreeNode *left;

TreeNode *right;

TreeNode *parent;

};

For example:

If 5 is deleted, then replace it with the maximum value in its left subtree which is 4. The final tree:

The function header ->

void deleteNode(TreeNode *node, int key);

Explanation / Answer

/* Given a binary search tree and a key, this function deletes the key
and returns the new root */
TreeNode* deleteNode(TreeNode root* , int key)
{
// base case
if (root == NULL) return root;

// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < root->key)
root->left = deleteNode(root->left, key);

// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (key > root->key)
root->right = deleteNode(root->right, key);

// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root->left == NULL)
{
TreeNode *temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL)
{
TreeNode *temp = root->left;
delete root;
return temp;
}

// node with two children: Get the inorder successor (smallest
// in the right subtree)
TreeNode* temp = minValueNode(root->right);

// Copy the inorder successor's content to this node
root->key = temp->key;

// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}

// helper function
/* Given a non-empty binary search tree, return the node with minimum
key value found in that tree. Note that the entire tree does not
need to be searched. */
TreeNode * minValueNode(TreeNode* node)
{
struct node* current = node;

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

return current;
}

Navigate

Write a C++ function to delete the given value from the binary search tree. The

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

Write a C++ function to delete the given value from the binary search tree. The

Question

Explanation / Answer

Related Questions

Navigate