When offering a menu option for user to choose to remove an employee in the binary tree, how do I code a remove method implementation where I ask user to input an Employee ID and traverse through the binary tree to find it and delete it. BRING6970 template 71 bool BinaryTree :: removeNode(int ID) {72737475 }76BinaryNode *nodePtr; 1 #ifndef BINARYTREE_H2 #define BINARYTREE_H3 #include "EmployeeData.h"4 #include 5 using namespace std;67 template 8class BinaryTree {9 private:1011121314151617181920212223242526272829struct BinaryNode {ItemType entry;BinaryNode *leftChildPtr;BinaryNode *rightChildPtr;};BinaryNode *rootPtr;void placeNode(BinaryNode *&, BinaryNode *&);void display InOrder (BinaryNode *) const;public:Binary Tree (){rootPtr = NULL; }void insertNode (ItemType);bool searchNode (int ID);bool removeNode(int ID);void display InOrder() const {displayInOrder (rootPtr):

Algorithm:Initialize a Binary Tree class with a nested BinaryNode structure.Implement methods to insert nodes, search for nodes, and display nodes in order.The placeNode method recursively places a new node in the appropriate position in the binary tree based on the ID.The displayInOrder method recursively displays nodes in ascending order of IDs.Create an instance of the BinaryTree class with the EmployeeData type.Insert nodes with employee data into the binary tree.Display the nodes in the order of their IDs.Prompt the user to enter an ID to search for in the binary tree.Output whether the ID is found or not.Source Code: C++ Programming:1#include <iostream> 2#include <string> 3 4using namespace std; 5 6// EmployeeData class for demonstration 7class EmployeeData { 8private: 9 int employeeID; 10 string employeeName; 11 12public: 13 EmployeeData(int id, const string& name) : employeeID(id), employeeName(name) {} 14 15 int getEmployeeID() const { 16 return employeeID; 17 } 18 19 string getEmployeeName() const { 20 return employeeName; 21 } 22 23 bool operator<(const EmployeeData& other) const { 24 return employeeID < other.employeeID; 25 } 26}; 27 28template <class ItemType> 29class BinaryTree { 30private: 31 struct BinaryNode { 32 ItemType entry; 33 BinaryNode* leftChildPtr; 34 BinaryNode* rightChildPtr; 35 }; 36 BinaryNode* rootPtr; 37 38 void placeNode(BinaryNode*&, BinaryNode*&); 39 void displayInOrder(BinaryNode*) const; 40 41public: 42 BinaryTree() { 43 rootPtr = NULL; 44 } 45 46 void insertNode(ItemType item) { 47 BinaryNode* newNode = new BinaryNode{item, nullptr, nullptr}; 48 placeNode(rootPtr, newNode); 49 } 50 51 bool searchNode(ItemType item) { 52 BinaryNode* nodePtr = rootPtr; 53 while (nodePtr) { 54 if (nodePtr->entry.getEmployeeID() == item.getEmployeeID()) { 55 return true; 56 } else if (item < nodePtr->entry) { 57 nodePtr = nodePtr->leftChildPtr; 58 } else { 59 nodePtr = nodePtr->rightChildPtr; 60 } 61 } 62 return false; 63 } 64 65 void displayInOrder() const { 66 displayInOrder(rootPtr); 67 } 68}; 69 70template <class ItemType> 71void BinaryTree<ItemType>::placeNode(BinaryNode*& nodePtr, BinaryNode*& newNode) { 72 if (nodePtr == NULL) 73 nodePtr = newNode; 74 else if (newNode->entry < nodePtr->entry) 75 placeNode(nodePtr->leftChildPtr, newNode); 76 else 77 placeNode(nodePtr->rightChildPtr, newNode); 78} 79 80template <class ItemType> 81void BinaryTree<ItemType>::displayInOrder(BinaryNode* nodePtr) const { 82 if (nodePtr != NULL) { 83 displayInOrder(nodePtr->leftChildPtr); 84 cout << "ID: " << nodePtr->entry.getEmployeeID() << ", Name: " << nodePtr->entry.getEmployeeName() << endl; 85 displayInOrder(nodePtr->rightChildPtr); 86 } 87} 88 89int main() { 90 BinaryTree<EmployeeData> binaryTree; 91 92 // Inserting nodes 93 binaryTree.insertNode(EmployeeData(1, "John")); 94 binaryTree.insertNode(EmployeeData(2, "Alice")); 95 binaryTree.insertNode(EmployeeData(3, "Bob")); 96 binaryTree.insertNode(EmployeeData(4, "Charlie")); 97 98 // Displaying in order 99 cout << "Displaying in order:" << endl; 100 binaryTree.displayInOrder(); 101 102 // Searching for a node 103 int searchID; 104 cout << "Enter ID to search: "; 105 cin >> searchID; 106 107 if (binaryTree.searchNode(EmployeeData(searchID, ""))) { 108 cout << "ID found!" << endl; 109 } else { 110 cout << "ID not found." << endl; 111 } 112 113 return 0; 114}Explanation:The program demonstrates the implementation of a binary tree to store and search for employee data using their IDs. It creates a binary tree, inserts employee nodes, displays them in ascending order of IDs, and allows the user to search for an employee by entering an ID. The program outputs whether the ID is found in the binary tree or not.Output