Help with C programming. I am having trouble writing the containsBSTree function

Question

Help with C programming.

I am having trouble writing the containsBSTree function.

/*
File: bst.c
Implementation of the binary search tree data structure.

*/
#include
#include
#include
#include
#include "bst.h"
//#include "structs.h"

struct Node {
TYPE val;
struct Node *left;
struct Node *right;
};

struct BSTree {
struct Node *root;
int cnt;
};

/*----------------------------------------------------------------------------*/
/*
function to initialize the binary search tree.
param tree
pre: tree is not null
post:   tree size is 0
root is null
*/

void initBSTree(struct BSTree *tree)
{
tree->cnt = 0;
tree->root = 0;
}

/*
function to create a binary search tree.
param: none
pre: none
post: tree->count = 0
tree->root = 0;
*/

struct BSTree* newBSTree()
{
struct BSTree *tree = (struct BSTree *)malloc(sizeof(struct BSTree));
assert(tree != 0);

initBSTree(tree);
return tree;
}

/*----------------------------------------------------------------------------*/
/*
function to free the nodes of a binary search tree
param: node the root node of the tree to be freed
pre: none
post: node and all descendants are deallocated
*/

void _freeBST(struct Node *node)
{
if (node != 0) {
   _freeBST(node->left);
   node->left = 0;
   _freeBST(node->right);
   node->right = 0;
   free(node);
}
}

/*
function to clear the nodes of a binary search tree
param: tree a binary search tree
pre: tree ! = null
post: the nodes of the tree are deallocated
tree->root = 0;
tree->cnt = 0
*/
void clearBSTree(struct BSTree *tree)
{
_freeBST(tree->root);
tree->root = 0;
tree->cnt = 0;
}

/*
function to deallocate a dynamically allocated binary search tree
param: tree the binary search tree
pre: tree != null;
post: all nodes and the tree structure itself are deallocated.
*/
void deleteBSTree(struct BSTree *tree)
{
clearBSTree(tree);
free(tree);
}

/*----------------------------------------------------------------------------*/
/*
function to determine if a binary search tree is empty.

param: tree the binary search tree
pre: tree is not null
*/
bool isEmptyBSTree(struct BSTree *tree) { return (tree->cnt == 0); }

/*
function to determine the size of a binary search tree

param: tree the binary search tree
pre: tree is not null
*/
int sizeBSTree(struct BSTree *tree) { return tree->cnt; }

/*----------------------------------------------------------------------------*/
/*
recursive helper function to add a node to the binary search tree.
param: cur   the current root node
val   the value to be added to the binary search tree
pre:   val is not null
*/
struct Node *_addNode(struct Node *cur, TYPE val)
{
/*write this*/

}
/*
function to add a value to the binary search tree
param: tree the binary search tree
val       the value to be added to the tree

pre:   tree is not null
val is not null
pose: tree size increased by 1
tree now contains the value, val
*/
void addBSTree(struct BSTree *tree, TYPE val)
{
tree->root = _addNode(tree->root, val);
tree->cnt++;
}

/*
function to determine if the binary search tree contains a particular element
param:   tree   the binary search tree
val       the value to search for in the tree
pre:   tree is not null
val is not null
post:   none
return true if val is in the tree, false if val is not in the tree
*/

/*----------------------------------------------------------------------------*/
bool containsBSTree(struct BSTree *tree, TYPE val)
{
/* write this */

}

/*
helper function to find the left most child of a node
return a pointer of the left most child of cur
param: cur       the current node
pre:   cur is not null
post: none
*/

/*----------------------------------------------------------------------------*/
struct Node *_leftMost(struct Node *cur)
{
/*write this*/
while (cur->left != 0)
   cur = cur->left;
return cur->val;

}

/*
recursive helper function to remove the left most child of a node
HINT: this function returns cur if its left child is NOT NULL. Otherwise,
it returns the right child of cur and free cur.

Note: If you do this iteratively, the above hint does not apply.

param: cur   the current node
pre:   cur is not null
post:   the left most node of cur is not in the tree
*/
/*----------------------------------------------------------------------------*/
struct Node *_removeLeftMost(struct Node *cur)
{
/*write this*/}

/*
recursive helper function to remove a node from the tree
param:   cur   the current node
val   the value to be removed from the tree
pre:   val is in the tree
cur is not null
val is not null
*/
/*----------------------------------------------------------------------------*/
struct Node *_removeNode(struct Node *cur, TYPE val)
{
/*write this*/

}
/*
function to remove a value from the binary search tree
param: tree the binary search tree
val       the value to be removed from the tree
pre:   tree is not null
val is not null
val is in the tree
pose:   tree size is reduced by 1
*/
void removeBSTree(struct BSTree *tree, TYPE val)
{
if (containsBSTree(tree, val)) {
   tree->root = _removeNode(tree->root, val);
   tree->cnt--;
}
}

/*----------------------------------------------------------------------------*/

/* The following is used only for debugging, set to "#if 0" when used
in other applications */
#if 1
#include

/*----------------------------------------------------------------------------*/
void printNode(struct Node *cur) {
if (cur == 0)
   return;
printf("(");
printNode(cur->left);
printNode(cur->right);
printf(")");
}

void printTree(struct BSTree *tree) {
if (tree == 0)
   return;
printNode(tree->root);
}
/*----------------------------------------------------------------------------*/

#endif

complete the recursive implementation of the binary search tree (BST) We are providing you with the following files (provided in this archive): bst.c is the file in which you'll finish implementing the unfinished BSTree. There is a main function in this file that you should modify thoroughly to exercise your BST. Because it is in the bst.c file, you can use it to test any internal as well as publicly accessible functions. Moreover, this file contains several test cases such as testAddNode(), testContainsBSTree(), testLeftMost(), ost(), and testRemo Your implemen tation should pass all these test cases.

Explanation / Answer

Function to check whether an element is present in a Binary Search Tree
  
bool containsBSTree(struct BSTree *tree, TYPE val)
{
//utility function to check whether the given value is present by passing tree Root
   return containsUtil(tree->root , val);

}

utility function for checking value is present in a tree by passing root to this fnction.
bool containsUtil(struct Node *root, TYPE val){

    //check if root contains this value
    if(root!= null && root-> val == val)return true;
  
  
    //check in left subTree
    if(val < root->val && root->left!=null && containsUtil(root->left, val)) {
      return true;
    }
  
    //check in the right subTree
    if(val > root->val && root->right!=null && containsUtil(root->right, val)){
       return true;
    }
  
    //By default return false if above cases fails.
    return false;
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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