HELP MY CODE IS WRONG Write a C++ function to delete the given value from the bi
ID: 3838337 • Letter: H
Question
HELP MY CODE IS WRONG
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.
You only need to consider the case where the node has two children. The node should be replaced by the minimum node in its right subtree.
void deleteAndReplaceMinRight(TreeNode *root, int key);
struct TreeNode
{
int key;
TreeNode *left;
TreeNode *right;
TreeNode *parent;
};
For example:
If the node to be deleted is 30, delete it and replace it with the minimum of its right subtree. Final tree:
My Answer:
void deleteAndReplaceMinRight(TreeNode *root, int key)
{
TreeNode *temp = root->right;
while(temp->left != NULL)
{
temp = temp->left;
root->key = temp->key;
if(temp->right == NULL)
{
temp->parent->left = NULL;
}
else
{
temp->parent->left = temp->right;
}
}
}
Feedback
Incorrect
Test Expected Got Input Tree:25
/
15 30
/
28 35
/ /
27 29 33 70
Delete 30
Expected Output:
25
/
15 33
/
28 35
/
27 29 70 Pre Order Traversal:
25 15 33 28 27 29 35 70
In Order Traversal:
15 25 27 28 29 33 35 70
Post Order Traversal:
15 27 29 28 70 35 33 25 Pre Order Traversal:
27 15 30 29 35 33 70
In Order Traversal:
15 27 29 30 33 35 70
Post Order Traversal:
15 29 33 70 35 30 27 Input Tree:
50
/
30 90
/
20 40
/
10 45
Delete 30
Expected Output:
50
/
40 90
/
20 45
/
10 Pre Order Traversal:
50 40 20 10 45 90
In Order Traversal:
10 20 40 45 50 90
Post Order Traversal:
10 20 45 40 90 50 Pre Order Traversal:
50 30 20 10 40 45 90
In Order Traversal:
10 20 30 40 45 50 90
Post Order Traversal:
10 20 45 40 30 90 50 Input Tree:
50
/
30 70
/
60 80
/
65 72
Delete 70
Expected Output:
50
/
30 72
/
60 80
65 Pre Order Traversal:
50 30 72 60 65 80
In Order Traversal:
30 50 60 65 72 80
Post Order Traversal:
30 65 60 80 72 50 Pre Order Traversal:
60 30 70 65 80 72
In Order Traversal:
30 60 65 70 72 80
Post Order Traversal:
30 65 72 80 70 60
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left, *right;
};
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
struct node* insert(struct node* node, int key)
{
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
struct node * minValueNode(struct node* node)
{
struct node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
struct node* deleteNode(struct node* root, int key)
{
if (root == NULL) return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else
{
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
struct node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
int main()
{
struct node *root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
printf("Inorder traversal of the given tree ");
inorder(root);
printf(" Delete 20 ");
root = deleteNode(root, 20);
printf("Inorder traversal of the modified tree ");
inorder(root);
printf(" Delete 30 ");
root = deleteNode(root, 30);
printf("Inorder traversal of the modified tree ");
inorder(root);
printf(" Delete 50 ");
root = deleteNode(root, 50);
printf("Inorder traversal of the modified tree ");
inorder(root);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.