Write a C++ program to validate computer user-ids and passwords. A list of valid ids and passwords (unsorted) is read from a file and stored in a Binary Search Tree (BST) of UserInfo objects. When user-ids and passwords are entered during execution, this BST is searched to determine whether they are legal. Input (file): UserInfo records for valid users Input (keyboard): Ids and passwords of users logging in Output (screen): Messages indicating whether user-ids and passwords are valid, as well as an alphabetical listing of all valid ids and passwords at the end of the run. Note: you will need to overload >>, <<, ==, and < operators in the UserInfo class in order to accomplish this task. BST.h class is on Blackboard. You may ONLY modify the search function. this is the BST.h file. i need the lab done by editing the this file. /* BST.h contains the declaration of class template BST. Basic operations: Constructor: Constructs an empty BST empty: Checks if a BST is empty search: Search a BST for an item insert: Inserts a value into a BST remove: Removes a value from a BST inorder: Inorder traversal of a BST -- output the data values Private utility helper operations: search2: Used by delete inorderAux: Used by inorder Other operations: destructor copy constructor assignment operator preorder, postorder, and level-by-level traversals level finder Note: Execution terminates if memory isn't available for a new BST node. ---------------------------------------------------------------------------*/ #include using namespace std; #ifndef BINARY_SEARCH_TREE #define BINARY_SEARCH_TREE template class BST { public: /***** Function Members *****/ BST(); /*------------------------------------------------------------------------ Construct a BST object. Precondition: None. Postcondition: An empty BST has been constructed. -----------------------------------------------------------------------*/ bool empty() const; /*------------------------------------------------------------------------ Check if BST is empty. Precondition: None. Postcondition: Returns true if BST is empty and false otherwise. -----------------------------------------------------------------------*/ bool search(const DataType & item) const; /*------------------------------------------------------------------------ Search the BST for item. Precondition: None. Postcondition: Returns true if item found, and false otherwise. -----------------------------------------------------------------------*/ void insert(const DataType & item); /*------------------------------------------------------------------------ Insert item into BST. Precondition: None. Postcondition: BST has been modified with item inserted at proper position to maintain BST property. ------------------------------------------------------------------------*/ void remove(const DataType & item); /*------------------------------------------------------------------------ Remove item from BST. Precondition: None. Postcondition: BST has been modified with item removed (if present); BST property is maintained. Note: remove uses auxiliary function search2() to locate the node containing item and its parent. ------------------------------------------------------------------------*/ void inorder(ostream & out) const; /*------------------------------------------------------------------------ Inorder traversal of BST. Precondition: ostream out is open. Postcondition: BST has been inorder traversed and values in nodes have been output to out. Note: inorder uses private auxiliary function inorderAux(). ------------------------------------------------------------------------*/ private: /***** Node class *****/ class BinNode { public: DataType data; BinNode * left; BinNode * right; // BinNode constructors // Default -- data part is default DataType value; both links are null. BinNode() { left = 0; right = 0;} // Explicit Value -- data part contains item; both links are null. BinNode(DataType item) { data = item; left = 0; right = 0; } };// end of class BinNode declaration typedef BinNode * BinNodePointer; /***** Private Function Members *****/ void search2(const DataType & item, bool & found, BinNodePointer & locptr, BinNodePointer & parent) const; /*------------------------------------------------------------------------ Locate a node containing item and its parent. Precondition: None. Postcondition: locptr points to node containing item or is null if not found, and parent points to its parent.#include ------------------------------------------------------------------------*/ void inorderAux(ostream & out, BinNodePointer subtreePtr) const; /*------------------------------------------------------------------------ Inorder traversal auxiliary function. Precondition: ostream out is open; subtreePtr points to a subtree of this BST. Postcondition: Subtree with root pointed to by subtreePtr has been output to out. ------------------------------------------------------------------------*/ /***** Data Members *****/ BinNodePointer myRoot; }; // end of class template declaration //--- Definition of constructor template inline BST::BST() {myRoot = 0;} //--- Definition of empty() template inline bool BST::empty() const { return myRoot == 0; } //--- Definition of search() template bool BST::search(const DataType & item) const { BinNodePointer locptr = myRoot; bool found = false; while (!found && locptr != 0) { if (item < locptr->data) // descend left locptr = locptr->left; else if (locptr->data < item) // descend right locptr = locptr->right; else // item found found = true; } return found; } //--- Definition of insert() template inline void BST::insert(const DataType & item) { BinNodePointer locptr = myRoot, // search pointer parent = 0; // pointer to parent of current node bool found = false; // indicates if item already in BST while (!found && locptr != 0) { parent = locptr; if (item < locptr->data) // descend left locptr = locptr->left; else if (locptr->data < item) // descend right locptr = locptr->right; else // item found found = true; } if (!found) { // construct node containing item locptr = new BinNode(item); if (parent == 0) // empty tree myRoot = locptr; else if (item < parent->data ) // insert to left of parent parent->left = locptr; else // insert to right of parent parent->right = locptr; } else cout << "Item already in the tree "; } //--- Definition of remove() template void BST::remove(const DataType & item) { bool found; // signals if item is found BinNodePointer x, // points to node to be deleted parent; // " " parent of x and xSucc search2(item, found, x, parent); if (!found) { cout << "Item not in the BST "; return; } //else if (x->left != 0 && x->right != 0) { // node has 2 children // Find x's inorder successor and its parent BinNodePointer xSucc = x->right; parent = x; while (xSucc->left != 0) // descend left { parent = xSucc; xSucc = xSucc->left; } // Move contents of xSucc to x and change x // to point to successor, which will be removed. x->data = xSucc->data; x = xSucc; } // end if node has 2 children // Now proceed with case where node has 0 or 2 child BinNodePointer subtree = x->left; // pointer to a subtree of x if (subtree == 0) subtree = x->right; if (parent == 0) // root being removed myRoot = subtree; else if (parent->left == x) // left child of parent parent->left = subtree; else // right child of parent parent->right = subtree; delete x; } //--- Definition of inorder() template inline void BST::inorder(ostream & out) const { inorderAux(out, myRoot); } //--- Definition of search2() template void BST::search2(const DataType & item, bool & found, BinNodePointer & locptr, BinNodePointer & parent) const { locptr = myRoot; parent = 0; found = false; while (!found && locptr != 0) { if (item < locptr->data) // descend left { parent = locptr; locptr = locptr->left; } else if (locptr->data < item) // descend right { parent = locptr; locptr = locptr->right; } else // item found found = true; } } //--- Definition of inorderAux() template void BST::inorderAux(ostream & out, BinNodePointer subtreeRoot) const { if (subtreeRoot != 0) { inorderAux(out, subtreeRoot->left); // L operation out << subtreeRoot->data << " "; // V operation inorderAux(out, subtreeRoot->right); // R operation } } #endif and this is an extra file called recrusive BST search i think we can use it as well. //--- Definition of search2() template void BST::search2(const DataType & item, bool & found) const { searchAUX(item, found, root); //begin searching at root } template void BST::searchAUX(const DataType & item, bool & found, BinNodePointer & locptr) const { if ( locptr == null ) // Failed to find found = false; // Base case 1 else if ( item < locptr->data ) // Down left searchAUX(item, found, locptr -> left); else if ( item > locptr->data ) // Down right searchAUX(item, found, locptr -> right); else // We FOUND it! found = true; // Base case 2 } we use c++. this is the second time to post this question. please make sure to use the trees to approach the answer. its due next monday and i have almost 3 finals i cant finish it.