Write a program in C++ to create a Binary Search tree (BST) of string data. The program will perform these operations: Insert name(s), Traverse Preorder, Search name, Delete name, Leaf Count, sibling of a person and Quit. Use this header file: class BT { private: struct node { string data; node* left; node* right; node* root; BT(); }; public: bool isEmpty() const { return root == NULL; } void insert(string); void print preorder(); void preorderTrav(node*); void searchBST (string); void deleteNode(string); int count(); int leafCount(node*); void nodeSibling(string); }; //Constructor //Check for empty //Insert item in BST //Preorder traversing driver //Preorder traversing //Searches BST for a specific node //Delete item in BST //Count driver //Counts number of leaves in BST //Finds sibling of a node Use the following menu in your program. Must place your name in the menu heading. MENU (YOUR NAME)- 1. Insert name(s) 2. Traverse Preorder 3. Search name 4. Delete name 5. Leaf Count 6. Sibling of a person 7. Quit Enter your choice: Use the following names in the given order to form the BST tree: KIM PAM DON TOM RON BEN AMY Option 1: Inserts name(s) in a BST. Option 2: Option 3: Enter Your Choice 1 Enter number of items to insert: 4 Enter node: KIM Inserted. Enter node: PAM Inserted. Enter node: DON Inserted. Enter node: TOM Inserted. Traverse the tree in Preorder and display the node info and its left child info and right child info. If a node does not have a child then display NIL. Enter Your Choice 2 Sample output: Traversing Preorder Node Info Left Child Info Right Child Info KIM DON PAM DON NIL NIL PAM NIL TOM NIL TOM NIL Search for the name in the BST. It will prompt: Enter name you want to search for: KIM If the name is found, then display the name and the left child information and right child information. If the item is not found, then it will display - " is not found in the BST" Node Info Left Child Info Right Child Info KIM DON PAM Option 4: Option 5: Option 6: Deletes a name from the BST. It will prompt: Enter name you want to delete: TOM If the name is found then delete the name from the BST and displays the message - " is deleted." If the name is not in the BST, then it will display - "_ is not found in the BST" TOM is deleted Counts the number of leaves in the BST and displays - "There are number of leaves in the BST." Enter a name and it will display the sibling of that person. It will prompt: Enter the name you want to find the sibling of: The sibling of is If the person has no sibling, then it displays: has no sibling. Ex: Enter the item: The sibling of PAM is DON. Option 7: Quit the program. PAM