C++

Do NOT use any of the STL in your code. You can use string functions for step 3. Do NOT write a class. For this lab, you should write a C++ program that creates a binary search tree based on user input. Use typedef to indicate the data type of the keys in the tree. Set the default type as string. The code should remain to work if typedef is changed to int after commenting out step 3. Use the following BSTNode struct for the tree. struct BSTNode { treeElement value; //key BSTNode* left; BSTNode* right; 1. Allow the user to add as many keys as they wish. Strings can be compared with symbols, similar to integers, based on the alphabetical order. The insert function should return whether the key is unique (i.e., return false if key is already in the tree): bool insert (BSTNode* & n, treeElement k); 2. Reverse print the tree starting from the right most node (i.e. Z to A). 3. Ask the user for a letter. Pass it to a function that returns how many nodes in the tree contain the letter. The function should use a preorder traversal. You can use any string function or a for loop to check each letter in the string. Check the execution example for reference. 4. Write a function to delete ALL of the nodes in the tree, including the root. Note that the recursive function doesn't set root to a nullptr so you'll have to handle it separately. Execution example [Labs]./lab3 How many values do you want to add to the BST? 6 Enter the value you want to insert: hello Enter the value you want to insert: class Enter the value you want to insert: have Enter the value you want to insert: a Enter the value you want to insert: nice Enter the value you want to insert: day! Reverse printing elements in the tree: nice hello have day! class a Enter a letter: a 4 nodes contain "a" The tree is empty now. Goodbye! After changing typedef to int [Labs)./lab3 How many values do you want to add to the BST? 5 Enter the value you want to insert: 1 Enter the value you want to insert: 4 Enter the value you want to insert: 2 Enter the value you want to insert: 7 Enter the value you want to insert: 3 Reverse printing elements in the tree: 7 4 3 2 1 The tree is empty now. Goodbye