Consider following Binary Search Tree (BST) implementation taken from some onlin
ID: 3735489 • Letter: C
Question
Consider following Binary Search Tree(BST) implementation taken from some online resource. Delete(treeNode *node, int data) deletes a node with value as data from the tree.
typedef struct treeNode
{
int data;
struct treeNode *left;
struct treeNode *right;
}treeNode;
//BST operations
treeNode* FindMin(treeNode *node)
treeNode* FindMax(treeNode *node)
treeNode * Insert(treeNode *node,int data)
treeNode * Find(treeNode *node, int data)
treeNode * Delete(treeNode *node, int data)
{
treeNode *temp;
if(node==NULL)
{
printf("Element Not Found");
}
else if(data < node->data)
{
node->left = Delete(node->left, data);
}
else if(data > node->data)
{
node->right = Delete(node->right, data);
}
else
{
if(node->right && node->left)
{
temp = FindMin(node->right);
node -> data = temp->data;
node -> right = Delete(node->right,temp->data);
}
else
{
temp = node;
if(node->left == NULL)
node = node->right;
else if(node->right == NULL)
node = node->left;
free(temp);
}
}
return node;
}
Understand the behavior of the function Delete(treeNode *node, int data).
Write 3 unit tests for this function. Try to cover as much of code as possible. Please, use proper assertions to verify your expected results.
Discuss if any code is missed to test after writing all 3 tests.
Notes:
You don’t need to use/run gcov to measure code coverage. Just simple discussion of coverage of the method using your unit tests will be sufficient.
You are provided few Binary Search Tree Operations at the beginning, use them to facilitate your testing. If they are not sufficient, just assume and use any Binary Search Tree operations you want to use to facilitate your test writing
Explanation / Answer
CODE IN C:
treeNode FindMin(treeNode node)
{
treeNode *temp = node;
while(temp->left)
temp = temp->left;
return temp;
}
treeNode FindMax(treeNode *node)
{
treeNode *temp = node;
while(temp->right)
temp = temp->right;
return temp;
}
treeNode Insert(treeNode node,int data)
{
if(node == NULL)
{
treeNode* temp = (treeNode*)malloc(sizeof(treeNode));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
if(data < node->data)
node->left = Insert(node->left, data); //creates node at left subtree if value is less than root
else
node->right = Insert(node->right, data); //creates node at right subtree if value is greater than root
return node;
}
treeNode Find(treeNode node, int data)
{
if (node == NULL || node->data == data)
return node;
if (node->data < data)
return search(node->right, data);
return search(node->left, data);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.