Write a C++ program that uses the binary tree definition in Figure 6.8 on page 220-222 (the file may be downloaded from the publisher website file name is genBST.h).

1. Add a function to the class to count the number of nodes in a binary tree

2. Add a function to the class to count the number of leaves in a binary tree

YOU MUST USE THE BINARY TREE DEFINITION AS LISTED IN THE BOOK. definition will not be accepted.

Create a program that uses this class as follows (The tree is used store strings names) 1. The program should present the user with a menu as follows:

Any other tree

1. Add a new name

2. Delete a name

3. List the contents in ascending order

4. Display the number of nodes in the tree

5. Display the number of leafs

6. Exit the system

Please enter your choice>

2. Create a function for each option on the menu to handle the request.

3. For choice # 1 (Add a new value), the function should prompt the user to enter a value (a

string). If the value is already stored in the tree, you should display a message that indicates

that.

4. For choice # 2 (Delete a value), the function should prompt the user to enter a value (a string).

Display a message to indicate if the value is found and deleted or if it is not found.

5. Main() should call a function called menu() to display the menu and return users input. Main()

should not handle any input or output other than reading and validating users input.

Note: The file downloaded from the publishers website contains a syntax error in deleteByCopying where a left ) is missing in "if (node->left== 0). Also, make sure to include using namespace std; and #include. Otherwise, the code does not compile.

FIGURE 6.8 Implementation of a generic binary search tree //***genBST.h* generic binary search tree #include #include queue> class Stack public stackI/ as in Figure 4.21 templatecclass T> class Queue public queuecT> public: T dequeue) T tmp front ) queue: :pop) return tmp; void enqueue (const T& el) push (el) templatecclass T> class BSTNode f public: BSTNode left = right = 0; el e; left l; right r; T el; BSTNodecT> left, *right; FIGURE 6.8 connued) templatecclass T class BST public: BST root-0 -BSTO clear ) void clear) clear (root); root 0; = bool isEmpty) const f return root -- 0; void preorder preorder (root) // Pigure 6.11 void inorder inorder (root); // Figure 6.11 void postorder) postorder (root) // Figure 6.11 T. search (const T& el) const return search (root,el); // Pigure 6.9 // Figure 6.10 // Figure 6.15 // Figure 6.17 // Figure 6.16 // Figure 6.20 /1 Figure 6.23 void deleteByMerging (BSTNodecT>*&): / Figure 6.29 void findAndDeleteByMerging (const T&) / Figure 6.29 // Figure 6.32 // Section 6.7 void breadthFirst void iterativePreorder ) void iterativeInorder: void iterativePostorder void MorrisInorder void insert (const T&) void deleteByCopying (BSTNodecD%); void balance (T*, int,int) protected: BSTNode) T* search (BSTNode*, const T&) const; // Figure 6.9 void preorder (BSTNode*) void inorder (BSTNode*) void postorder (BSTNode) virtual void visit (BSTNodeel