Complete the implementation of the BST.c . There are 6 functions to implement: _
ID: 665848 • Letter: C
Question
Complete the implementation of the BST.c. There are 6 functions to implement:
_createNode
_heightOfSubTree
_addNodeToSubTree
_containsSubTree
_removeLeftMost
_removeNodeFromSubtree
Note that these functions are all private (note the _), and that the public functions which call the private functions have all been written for you.
None of these functions are particularly long, but they can be a bit time consuming to write since they often use recursion to traverse down the tree to an area of interest, then assign returned pointers as function calls return in order to put the tree back together.
FILES YOU WILL NEED:
//BST.h
//BST.c
//type.h
//main.c
ERRATA
The makefile does not link the C library math.h properly, change the lines that read
To read as follows
Note the addition of -lm.
Delete the following lines from main.c:
Explanation / Answer
The required completed methods are:-
Node* _createNode(node ** tree, int val)
{
node *temp=NULL;
if(!(*tree)) {
temp=(node *)malloc(sizeof(node));
temp->left=temp->right = NULL;
temp->data=val;
*tree=temp;
return;
}
if(val<(*tree)->data) {
_createNode(&(*tree)->left,val);
} else if(val>(*tree)->data){
_createNode(&(*tree)->right,val);
}
}
int _heightOfSubTree(Node* root)
{
if (root==NULL)
return 0;
else
{
/* compute the depth of every subtree */
int lDepth = _heightOfSubTree(root->left);
int rDepth = _heightOfSubTree(root->right);
/* use the greater one */
if (lDepth > rDepth)
return(lDepth+1);
else
return(rDepth+1);
}
}
Node* _addNodeToSubtree(Node* curr, int val)
{
node *temp=NULL;
if(!(curr)) {
temp=(node *)malloc(sizeof(node));
temp->left=temp->right = NULL;
temp->data=val;
curr=temp;
return;
}
if(val<(curr)->data) {
_addNodeToSubtree(&(curr)->left,val);
} else if(val>(curr)->data){
_addNodeToSubtree(&(curr)->right,val);
}
}
int _containsSubTree(struct node *A,struct node *B)
{
if (B == NULL)
return true;
if (A == NULL)
return false;
if (areIdentical(A,B))
return true;
return _containsSubTree(A->left,B)||_containsSubTree(A->right,B);
}
Node* _removeNodeFromSubtree(Node* curr, int val)
{
if (curr==NULL)
return curr;
if (val<curr->val)
curr->left=_removeNodeFromSubtree(curr->left,val);
else if (val>curr->val)
curr->right=_removeNodeFromSubtree(curr->right,val);
else
{
if(curr->left==NULL)
{
struct node *temp=curr->right;
free(curr);
return temp;
}
else if(curr->right==NULL)
{
struct node *temp=curr->left;
free(curr);
return temp;
}
struct node* temp=minimumValueNode(curr->right);
curr->val=temp->val;
curr->right=_removeNodeFromSubtree(curr->right,temp->val);
}
return curr;
}
struct node * minimumValueNode(struct node* node)
{
struct node* curr=node;
while (curr->left != NULL)
curr=curr->left;
return curr;
}