Main.c is provided:

#include "bst.h" #include "stdio.h" #include "stdlib.h" #include "time.h" void inputTest();

void heightExperiments(); int minV(int *A, int size); int maxV(int *A, int size); int readNumber(); 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; }

// Students must implement this function void heightExperiments() { printf("Implement Me! "); } bst.h is given:

#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 Q) There is data structure and function prototypes for a binary search three. The program is missing the bst.c file. I need 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: