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.

ONLY 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

Given below is a C++ solution for given problem. Comments are added in code for readability. Sample execution output is given below for reference. In addition to deleteAndReplaceLeftMin, implementation of methods addTreeNode and printTree methods are provided for completeness.

File: Main.cpp

#include <iostream>
using namespace std;

/*
* Represents a node in a Tree.
*/
typedef struct TreeNode
{
int key;

TreeNode *left;
TreeNode *right;
TreeNode *parent;

TreeNode(int aKey, TreeNode *aParent)
{
key = aKey;
left = NULL;
right = NULL;
parent = aParent;
}
} TreeNode;

/*
* Add a node to given binary search tree.
*/
bool addTreeNode(TreeNode * & root, int key)
{
if (root == NULL)
{
// If given tree is empty, new node created is the tree root.

root = new TreeNode(key, NULL);
}
else
{
TreeNode *temp = root;

while (true)
{
// Duplicates are not allowed in our binary search tree.

if (key == temp->key) return false;

// If key is less than key of temp node then new node
// needs to be created in left subtree of temp. Otherwise,
// new node needs to be created in right subtree of temp.

if (key < temp->key)
{

if (temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = new TreeNode(key, temp);
return true;
}
}
else if (temp->right != NULL)
{
temp = temp->right;
}
else
{
temp->right = new TreeNode(key, temp);
return true;
}
}
}
}

/*
* Find node with given key. Delete found node's right child and
* replace with node having minimum value in its left subtree.
*/
bool deleteAndReplaceLeftMin(TreeNode * root, int key)
{
// Find node with given key

TreeNode *foundNode = root;

while (true)
{
if (foundNode == NULL) break;

if (key == foundNode->key)
{
break;
}
else if (key < foundNode->key)
{
foundNode = foundNode->left;
}
else
{
foundNode = foundNode->right;
}
}

if (foundNode == NULL) return false;

TreeNode *rightNode = foundNode->right;

if (rightNode == NULL) return false;

// Find node having minimum value in found node's right child's left subtree

TreeNode *foundLeftSubTreeMinNode = rightNode;

while (foundLeftSubTreeMinNode->left != NULL)
{
foundLeftSubTreeMinNode = foundLeftSubTreeMinNode->left;
}

if (foundLeftSubTreeMinNode == rightNode) return false;

// Delete found node's right child and replace with node having minimum value in its left subtree

foundLeftSubTreeMinNode->parent->left = foundLeftSubTreeMinNode->right;
rightNode->parent->right = foundLeftSubTreeMinNode;
foundLeftSubTreeMinNode->left = rightNode->left;
foundLeftSubTreeMinNode->right = rightNode->right;

return true;
}

/*
* Print given tree in pre order.
*/
void printPreOrder(TreeNode *node)
{
if (node == NULL) return;

cout << node->key << " ";
printPreOrder(node->left);
printPreOrder(node->right);
}

/*
* Print given tree.
*/
void printTree(TreeNode *node)
{
cout << "Tree: ";
printPreOrder(node);
cout << endl;
}

int main() {
TreeNode* root = NULL;

addTreeNode(root, 25);

addTreeNode(root, 15);
addTreeNode(root, 8);
addTreeNode(root, 20);

addTreeNode(root, 30);
addTreeNode(root, 28);
addTreeNode(root, 35);
addTreeNode(root, 27);
addTreeNode(root, 29);

printTree(root);

cout << "Delete right child of node with key 25" << endl;

deleteAndReplaceLeftMin(root, 25);

printTree(root);

return 0;
}

Sample Execution Output:

Tree: 25 15 8 20 30 28 27 29 35
Delete right child of node with key 25
Tree: 25 15 8 20 27 28 29 35

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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