Complete the implementation of the BST.c . There are 6 functions to implement: _

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;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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