CSCE 350: Data Structures and Algorithms Homework - 3 Task-1: {40 points) I Write a C++ program to implement a Binary Search Tree. Your program must allow the user to perform the following tasks: 0 Accept values from the user to insert into the binary search tree - The rst node entered by the user becomes the root node 0 Allow the user to delete nodes from the binary search tree 0 Allow the user to search for a node within the binary search tree: I If the search key is found. it returns all the nodes visitedipath traversed} to reach the search key. I If search key is not found, returns the path traversed to locate the search key and indicates a failed search. 0 File Name: BinarySearchTree_YourLastName_YourFirstName.cpp BinarySearchTree.cpp C+ BinarySearchTree.cpp > ... #include using namespace std; struct node int key; struct node *left, *right; 8 9 10 void inorder(struct node *root) 11 12 14 15 struct node* insert (struct node* node, int key) 16 17 18 19 20 struct node* deleteNode (struct node* root, int key) { 25 void printPath (struct node *root, int key, vector&v) 26 27 28 29 30 int main( ) 31 { 32 33 int ch, key; 34 struct node *root = NULL; vectorv; 36 37 while(1) 38 39 cout>ch;36 37 while(1) 38 39 cout>ch; 50 51 v switch (ch) 52 53 case 1: cout>key; 55 root = insert(root, key); 56 break; 57 58 case 2: cout >key; 60 root = deleteNode ( root, key); 61 break; 62 63 case 3: cout>key; 65 printPath ( root, key, v) ; 66 if (v. size()>0) 68 cout>key; 60 root = deleteNode ( root, key) ; 61 break; 62 63 case 3: cout >key; 65 printPath ( root, key, v) ; 66 if (v. size()>0) 67 68 cout