We CANNOT change the BST.h and Main.c files nor add anything further.

You are provided with two files. There is data structure and function prototypes for a binary search three in bst.h. You are also given a test file in main.c for the BST. It has two possible tests. In this part of the assignment, you will only use option 1. The program is missing the bst.c file. Your job it to create this file and implement everything described in bst.h. When running the program you will be asked which option to select. For this part select 1. Then you can enter numbers and a BST will be made with those numbers. Example Output % ./main Select Option: 1.) Enter Tree Values and print tree. 2.) Run Height Experiments. 1 Enter Number of Values to Test: 7 Enter A[0] value: 6 Enter A[1] value: 4 Enter A[2] value: 1 Enter A[3] value: 10 Enter A[4] value: 8 Enter A[5] value: 5 Enter A[6] value: 12 Inserted 6 into tree Preorder: 6 Inorder: 6 Postorder: 6 Inserted 4 into tree Preorder: 6 4 Inorder: 4 6 Postorder: 4 6 Inserted 1 into tree Preorder: 6 4 1 Inorder: 1 4 6 Postorder: 1 4 6 Inserted 10 into tree Preorder: 6 4 1 10 Inorder: 1 4 6 10 Postorder: 1 4 10 6 Inserted 8 into tree Preorder: 6 4 1 10 8 Inorder: 1 4 6 8 10 Postorder: 1 4 8 10 6 Inserted 5 into tree Preorder: 6 4 1 5 10 8 Inorder: 1 4 5 6 8 10 Postorder: 1 5 4 8 10 6 Inserted 12 into tree Preorder: 6 4 1 5 10 8 12 Inorder: 1 4 5 6 8 10 12 Postorder: 1 5 4 8 12 10 6 The Tree Height is 2 Is 0 in the tree? Answer: 0 Is 1 in the tree? Answer: 1 Is 2 in the tree? Answer: 0 Is 3 in the tree? Answer: 0 Is 4 in the tree? Answer: 1 Is 5 in the tree? Answer: 1 Is 6 in the tree? Answer: 1 Is 7 in the tree? Answer: 0 Is 8 in the tree? Answer: 1 Is 9 in the tree? Answer: 0 Is 10 in the tree? Answer: 1 Is 11 in the tree? Answer: 0 Is 12 in the tree? Answer: 1 Delete 6 from tree Preorder: 8 4 1 5 10 12 Inorder: 1 4 5 8 10 12 Postorder: 1 5 4 12 10 8 Delete 4 from tree Preorder: 8 5 1 10 12 Inorder: 1 5 8 10 12 Postorder: 1 5 12 10 8 Delete 1 from tree Preorder: 8 5 10 12 Inorder: 5 8 10 12 Postorder: 5 12 10 8 Delete 10 from tree Preorder: 8 5 12 Inorder: 5 8 12 Postorder: 5 12 8 Delete 8 from tree Preorder: 12 5 Inorder: 5 12 Postorder: 5 12 Delete 5 from tree Preorder: 12 Inorder: 12 Postorder: 12 Delete 12 from tree Preorder: Inorder: Postorder:

bst.h file:

//----You MAY NOT change this file ------- #ifndef _BST_H_ #define _BST_H_ /** A structure to represent a single node in a binary search tree. */ struct Node{ int value; /**< The value at this point in the tree.*/ struct Node* left; /**< The left child of this node.*/ struct Node* right; /**< The right child of this node.*/ }; //Give the struct a short name typedef struct Node Node; /** A structure to represent a binary search tree. */ struct BST{ Node* root; /** The root node of the binary tree.*/ }; typedef struct BST BST; //Front End Methods //These method act on the TREE starting at the root /** Create a new empty Binary Search Tree @return Pointer to empty BST */ BST* newBST(); /** Free all the memory allocated to the BST @param T is the tree to delete from memory */ void deleteBST(BST* T); /** Insert a value into the BST. Ignore duplicates. @param T is the tree to insert into @param target is the value to insert */ void insert(BST* T, int target); /** Find a value in the BST. @param T is the tree to search @param target is the value to search for @return 1 if found and 0 if not in tree */ char find(BST* T, int target); /** Delete a value from the tree @param T is the tree to delete from @param target is the value to delete */ void deleteFromTree(BST* T, int target); /** Find the Minimum in the BST. @param T is the tree to search for the min @return The smallest number in the tree */ int min(BST* T); /** Print the tree in inorder to stdout. End with newline @param T is the tree to print */ void inorder(BST* T); /** Print the tree in preorder to stdout. End with newline @param T is the tree to print */ void preorder(BST* T); /** Print the tree in postorder to stdout. End with newline @param T is the tree to print */ void postorder(BST* T); /** Find the height of the tree. @param T is tree to check the height on @param The number of edges in longest path to root. -1 for null tree. */ int height(BST* T); //These methods act on Nodes //They can be implemented recursively. /** Recursively print the tree inorder. End with a space. @param current is the node to print */ void inorderWalker(Node* current); /** Recursively print the tree preorder. End with a space. @param current is the node to print */ void preorderWalker(Node* current); /** Recursively print the tree postorder. End with a space @param current is the node to print */ void postorderWalker(Node* current); /** Insert a value starting at a node recursively. @param target is the value to insert @param current is the node to start at @return Updated pointer to node after changes */ Node* insertValue(int target, Node* current); /** Find a value in the tree starting at node recursively. @param target is the value to search for @param current is the node to start at @return 1 if found and 0 if not found */ char findValue(int target, Node* current); /** Find the minimum value starting at node recursively @param current is the node to start looking at @return The minimum of the section of the three starting at current */ int findMin(Node* current); /** Find the height of a node. Null has height -1. @param current is the node to find the height of @return The height of the node in question */ int nodeHeight(Node* current); /* Delete a value from the BST starting at node recursively. @param target is the value to delete @param current is the node to start at @return The updated node pointer */ Node* deleteValue(int target, Node* current); /** Delete a specific node. @param current is the node to delete @return Updated pointer to replace node in the tree */ Node* deleteNode(Node* current); #endif

main.c file:

//---Make no other changes--- #include "bst.h" #include "stdio.h" #include "stdlib.h" #include "time.h" /** Ask user for a list of numbers. Test BST with them. */ void inputTest(); /** Generate Random Trees and test heights. Print table of resuts. */ void heightExperiments(); /** Find Minimum in an Array @param A is the array to search @param size is the array size @return The minimum element in array */ int minV(int* A, int size); /** Find Maximum in an Array @param A is the array to search @param size is the array size @return The max element in array */ int maxV(int* A, int size); /** Read an integer from stdin. Consumes all characters till newline @return Integer read */ int readNumber(); /** Test file for student BST code @param argc not used @param argv not used @return 0 on success and 1 on bad input */ int main(int argc, char** argv){ //Set random number generator srand(time(NULL)); //Users has two options printf("Select Option: "); printf("1.) Enter Tree Values and print tree. "); printf("2.) Run Height Experiments. "); //Read the users answer int r=readNumber(); if(r < 1 || r > 2){ printf("Bad Input. Try Again. "); return 1; } if(r==1){ inputTest(); return 0; } if(r==2){ heightExperiments(); return 0; } return 0; } //Get an array of numbers from user. //Insert, Find and Delete All of them. void inputTest(){ //Ask for Size (assume good input) printf("Enter Number of Values to Test: "); int testSize=readNumber(); //read values int* A = malloc(sizeof(int)*testSize); for(int i=0; i < testSize;i++){ printf("Enter A[%d] value: ",i); A[i] = readNumber(); } //First, make an empty tree BST* B = newBST(); //Insert some numbers to make an expected tree for(int i=0; i < testSize; i++){ insert(B,A[i]); printf("Inserted %d into tree ",A[i]); printf("Preorder: "); preorder(B); printf("Inorder: "); inorder(B); printf("Postorder: "); postorder(B); } //Check the height printf("The Tree Height is %d ",height(B)); //Check find int smallest = minV(A,testSize); int largest = maxV(A,testSize); for(int i=smallest-1; i < largest+1; i++){ printf("Is %d in the tree? ",i); printf("Answer: %d ",find(B,i)); } //Delete the values in order for(int i=0; i < testSize; i++){ deleteFromTree(B,A[i]); printf("Delete %d from tree ",A[i]); printf("Preorder: "); preorder(B); printf("Inorder: "); inorder(B); printf("Postorder: "); postorder(B); } //Clear Memory deleteBST(B); return; } int minV(int* A, int size){ int myMin = 9999; for(int i=0; i < size; i++){ if(A[i] < myMin){ myMin = A[i]; } } return myMin; } int maxV(int* A, int size){ int myMax = -9999; for(int i=0; i < size; i++){ if(A[i] > myMax){ myMax = A[i]; } } return myMax; } //Read a number from STDIN int readNumber(){ int number=0; char c = getchar(); while(c!=' '){ number = number*10+(c-48); c = getchar(); } return number; }

This is my bst.c file I had written:

#include #include #include "bst.h" /** Create a new empty Binary Search Tree @return Pointer to empty BST */ BST* newBST(){ //Allocate a new BST and get pointer BST* T = malloc(sizeof(struct BST)); //Set the root to be empty T->root = NULL; //Return pointer to tree return T; } void deleteBST(BST *T){ free(T); } void insert(BST *T, int target){ //This might change the root node T->root = insertValue(target, T); } char find(BST *T, int target){ //Start recursive search at the root return find(target, T->root); } void deleteFromTree(BST *T, int target){ T = deleteValue(target, T); } int min(BST *T){ return findMin(T->root); } /** Print the tree in inorder to stdout. End with newline @param T is the tree to print */ void inorder(BST *T){ if (T != NULL) return; inorder(T->root->left); printf("%d ", T->root->value, " "); inorder(T->root->right); } /** Print the tree in preorder to stdout. End with newline @param T is the tree to print */ void preorder(BST *T){ if (T != NULL) return; printf("%d ", T->root->value, " "); preorder(T->root->left); preorder(T->root->right); } /** Print the tree in postorder to stdout. End with newline @param T is the tree to print */ void postorder(BST *T){ if (T != NULL) return; postorder(T->root->left); postorder(T->root->right); printf("%d ", T->root->value, " "); } int height(BST *T){ //The tree height is the node height of the root return height(T->root); } /** Recursively print the tree inorder. End with a space. @param current is the node to print */ void inorderWalker(Node *current){ if (current != NULL) return; preorder(current->left); printf("current->value "); preorder(current->right); } /** Recursively print the tree preorder. End with a space. @param current is the node to print */ void preorderWalker(Node *current){ if (current != NULL) return; printf(current->value); preorder(current->left); preorder(current->right); } /** Recursively print the tree postorder. End with a space @param current is the node to print */ void postorderWalker(Node *current){ if (current != NULL) return; preorder(current->left); preorder(current->right); printf("current "); } Node *insertValue(int target, Node *current){ //If we are an empty position, create a new node if (current == NULL){ Node* newNode = malloc(sizeof(struct Node)); newNode->value = target; newNode->left = 0; newNode->right = 0; return newNode; } //If the value is found, ignore it if (current->value == target){ return current; //No Changes } //Recursively update either left or right side if (current == target){ //Insert and update on left current->left = insertValue(target, current->left); //Return updated node return current; } //Insert and update on right current->right = insertValue(target, current->right); //Return updated node return current; } /** Find a value in the tree starting at node recursively. @param target is the value to search for @param current is the node to start at @return 1 if found and 0 if not found */ char findValue(int target, Node *current){ //If the node is empty then nowhere to look. if (current == NULL){ return 0; } //If the value is the current node, we found target if (current->value == target){ return 1; } //Otherwise, compare and search one side. if (current->value > target){ //Node is to big, search left return find(target, current->left); } //Node is to small, search right return find(target, current->right); } /** Find the minimum value starting at node recursively @param current is the node to start looking at @return The minimum of the section of the three starting at current */ int findMin(Node *current){ //Return -1 for error if (current == NULL){ return -1; } //If no left child then at min if (current->left == 0){ return current->value; } //Otherwise keep searching return findMin(current->left); } int nodeHeight(Node *current){ if (current == NULL){ return -1; } int leftHeight = nodeHeight(current->left); int rightHeight = nodeHeight(current->right); if (leftHeight > rightHeight){ return leftHeight += 1; } return rightHeight += 1; } Node *deleteValue(int target, Node *current){ //Case 1: Empty Node if (current == NULL){ return 0; } //Case 2: This is the node we want if (current->value == target){ int x = deleteNode(current); return x; } //Case 3: Search left or right for target if (current->value > target){ //Search left current->left = deleteValue(target, current->left); return current; } //Search right current->right = deleteValue(target, current->right); return current; } Node *deleteNode(Node *current){ //Case 1: If no left child then replace with right child if (current->left == NULL){ return current->right; } //Case 2: If no right child then replace with left child if (current->right == NULL){ return current->left; } //Case 3: Swap with min value on right side int minVal = findMin(current->right); //Swap min here current->value = minVal; //Delete from right side current->right = deleteValue(minVal, current->right); //Return updated pointer return current; }

Thanks in advanced, been on this for over 4 days.