Write a program in C++ to create a Binary Search tree (BST) of integers. The program will perform these operations: Insert node(s), Traverse In-order, Search node, Delete node, Leaf Count, Parent of a node and Quit Use the header file similar to this: #include #ifndef BT H #define BTH using namespace std; class BT private: struct node int data; node* left; node* right; l; node* root; public: BT); bool isEmpty) const return rootNULL void insert (int); void print_inorder(); void inorderTrav (node); void searchBST (int) void deleteNode(int) int count(); int leafCount (node*); void nodeParent(int); //Constructor //Check for empty //Insert item in BST //In-order traversing driver //In-order traversing //Searches BST for a specific node //Delete item from BST //Count driver //Counts number of leaves in BST //Finds parent of a node tend if Use the following menu in your program MENU 1.Insert node(s) Traverse In-order Search node Delete node Leaf Count Parent of a node 4 7.Quit Enter your choice Use the following characters in the given order to form the BST tree 20 10 15 30 25 40 0 5 35 Hints: 1. Before you start working on the program, you draw the BST for the given order of the above characters. It will help you check your output for the options in the menu. 2. While working on the program, use enter few items for testing-such as 20 10 15 30, 3. You work on one menu at a time then it is easier to test and manage the program instead of writing the whole program for entire menu then test your program.) Option 1:Inserts node(s) in a BST Enter Your Choice 2 Sample output: Traversing In-order Left Child Info Node Info Right Child Info 10 15 20 30 NIL NIL 10 NIL 15 NIL 30 NIL Option 3 Search for the item in the BST It will prompt: Enter item you want to search for: 10 If the item is found, then display the message-is found in the BST. If the item is not found then it will display -"is not found in the BST" 10 is found in the BST Deletes a node from the BST It will prompt: Enter item you want to delete: 30 Option 4: If the item is found then delete the item from the BST and displays the message - "is deleted." If the item is not in the BST, then it will display -"is not found in the BST" 30 is deleted Counts the number of leaves in the BST and displays "There are number of leaves in the BST." Option 5: Enter the item and it will display the Parent of that item. It will prompt: Enter the item you want to find the Parent of: Option 6: The parent of is If the item has no parent then it displays: IS has no parent. Ex Enter the item: 10 The parent of 10 is 20 Option 7: Quit the program. Write a program in C++ to create a Binary Search tree (BST) of integers. The program will perform these operations: Insert node(s), Traverse In-order, Search node, Delete node, Leaf Count, Parent of a node and Quit Use the header file similar to this: #include #ifndef BT H #define BTH using namespace std; class BT private: struct node int data; node* left; node* right; l; node* root; public: BT); bool isEmpty) const return rootNULL void insert (int); void print_inorder(); void inorderTrav (node); void searchBST (int) void deleteNode(int) int count(); int leafCount (node*); void nodeParent(int); //Constructor //Check for empty //Insert item in BST //In-order traversing driver //In-order traversing //Searches BST for a specific node //Delete item from BST //Count driver //Counts number of leaves in BST //Finds parent of a node tend if Use the following menu in your program MENU 1.Insert node(s) Traverse In-order Search node Delete node Leaf Count Parent of a node 4 7.Quit Enter your choice Use the following characters in the given order to form the BST tree 20 10 15 30 25 40 0 5 35 Hints: 1. Before you start working on the program, you draw the BST for the given order of the above characters. It will help you check your output for the options in the menu. 2. While working on the program, use enter few items for testing-such as 20 10 15 30, 3. You work on one menu at a time then it is easier to test and manage the program instead of writing the whole program for entire menu then test your program.) Option 1:Inserts node(s) in a BST Enter Your Choice 2 Sample output: Traversing In-order Left Child Info Node Info Right Child Info 10 15 20 30 NIL NIL 10 NIL 15 NIL 30 NIL Option 3 Search for the item in the BST It will prompt: Enter item you want to search for: 10 If the item is found, then display the message-is found in the BST. If the item is not found then it will display -"is not found in the BST" 10 is found in the BST Deletes a node from the BST It will prompt: Enter item you want to delete: 30 Option 4: If the item is found then delete the item from the BST and displays the message - "is deleted." If the item is not in the BST, then it will display -"is not found in the BST" 30 is deleted Counts the number of leaves in the BST and displays "There are number of leaves in the BST." Option 5: Enter the item and it will display the Parent of that item. It will prompt: Enter the item you want to find the Parent of: Option 6: The parent of is If the item has no parent then it displays: IS has no parent. Ex Enter the item: 10 The parent of 10 is 20 Option 7: Quit the program