In C language please. In this programming assignment, you will write a program that creates a binary search tree (BST) based on user input. Then, the user will indicate what order to print the values in.

Start with the bst.h and bst.c base code provided to you in class, without the print functions. You will need to modify the source and header file to complete this assignment. Starting files are provided as attachments.

In the header file bst.h, do the following:

• Add a enum named BSTOrder which will create enumerators for each of the three BST orders. The enumerators are PREORDER, INORDER, and POSTORDER. Use the same ordering of these enumerators in your declaration.
• Declare prototype for a traversal function named traverseBST().

In the source file bst.c, do the following:

• Write the traversal function named traverseBST() that will take in two parameters: a pointer to a BSTNode and a BSTOrder enumerator.
• This function will print out all the values in the binary search tree in the order that is determined by its BSTOrder parameter.
• It will recursively traverse the binary search tree and print out each value separated by a space.
• You should not create any separate functions for the traversals. The code should all be the same for the traversal, however the printing will depend on the order type selected. Use the BSTOrder parameter to indicate when the print will happen.

Create a main.c source file with the main() that will do the following:

• Prompt the user for how many values they want to enter into the binary search tree.
• Next, prompt the user to enter values which will then be inserted in the binary search tree. Assume that the user will always enter an integer.
• Lastly, ask the user to enter which order they want to print their tree. For simplicity, assume that the user will enter either of 0 for PREORDER, 1 for INORDER, or 2 for POSTORDER. These are also the default values for the enumerators.
• The program will then print out the binary search tree in the desired order selected by the user. Each integer value in the tree is separated by a tab.
• De-allocate and delete the binary search tree at the end of the program.

Example Output: for the tree print the values are separated by tabs. Your output should also following the same format as shown below

Enter the number of nodes for the tree: 7Enter a node value: 60Enter a node value: 30Enter a node value: 20Enter a node value: 50Enter a node value: 80Enter a node value: 90Enter a node value: 70Enter the order for traversal and printing (0-Preorder, 1-Inorder, 2-Postorder): 120 30 50 60 70 80 90

#include #include #include\"bst.h\"

/* Function: create ------------------- This function creates a new BSTNode. v: the value to be addeded to the tree Returns: New node for a Binary Search Tree */ BSTNode* create(int v) { BSTNode* n = (BSTNode*)malloc(sizeof(BSTNode)); n->value = v; n->left = NULL; n->right = NULL; return n; }

/* Function: insert ------------------- This function inserts a new BSTNode. root: root of current subtree n: node to be inserted Returns: Root a Binary Search Tree */ BSTNode* insert(BSTNode* root, BSTNode* n) { if(root == NULL) return n; else if(n->value value) root->left = insert(root->left, n); else root->right = insert(root->right, n); return root; }=>

/* Function: deleteBST ------------------- This function deallocates all the nodes in the BST root: root of the tree/subtree Returns: NULL */ BSTNode* deleteBST(BSTNode* root) { if(root == NULL) return NULL; deleteBST(root->left); deleteBST(root->right); /* if we reach here, root is a leaf, so free it */ free(root); return NULL; }

/* Function: find ------------------- This function finds if a key value exists in a binary search tree. root: root of the tree/subtree key: key value we are looking for Returns: pointer to the node in which the value x was found */ BSTNode* find(BSTNode* root, int key) { if(root == NULL || root->value == key) return root; else if(key value) return find(root->left, key); else return find(root->right, key); }

/* Function: removeNode ------------------- This function removes a node with a specific value in a binary search tree. root: root of the tree/subtree key: key value we are looking for that will be removed Returns: root of the tree/subtree */ BSTNode* removeNode(BSTNode* root, int key) { if(root == NULL ) return NULL; /* if key value is less than the current root's value, search to left */ if(key value) root->left = removeNode(root->left, key); /* if key value is greater than the current root's value, search to right */ else if(key > root->value) root->right = removeNode(root->right, key); /* if the value was found */ else if(root->value == key) { /* the following if statements check the current root's descendents. there is a different set of actions depending. */ if(root->left == NULL && root->right == NULL) { free(root); return NULL; } /* if either of left or right child is null return the one that exists. */ else if(root->left == NULL || root->right == NULL) { BSTNode* tmp; if(root->left == NULL) tmp = root->right; else tmp = root->left; free(root); return tmp; } /* find the left most child. Assign that value to the root (the node) to be removed. Remove the actual successor node. */ else { BSTNode* tmp = root->right; while(tmp->left != NULL) tmp = tmp->left; root->value = tmp->value; root->right = removeNode(root->right, tmp->value); } } return root; }

#ifndef BST_H #define BST_H

typedef struct BSTNode { int value; struct BSTNode *left; struct BSTNode *right; } BSTNode;

BSTNode* insert(BSTNode*, BSTNode*); BSTNode* create(int); BSTNode* find(BSTNode*, int); BSTNode* removeNode(BSTNode*, int); BSTNode* deleteBST(BSTNode*);

#endif