In C++

Implement the BinarySearchTree ADT in a file BinarysearchTree.h exactly as shown below // BinarySearchTree.h // after Mark A. bleiss, Chapter 4, Dr. Kerstin Voigt #ifndef BINARY SEARCH TREE H #define BINARYSEARCHTREEH - - - #include using namespace std; template element; const C& findMax( const assert(!isEmpty ()); return findMax( root )->element; bool contains( const C& x) const return contains( x, root); bool isEmpty const return rootnullptr; void printTree( ) const if( isEmpty()) out element else if( t->element left); insert( x, t->right ); ; // Duplicate; do nothing Internal method to remove from a subtree. / x is the item to remove // t is the node that roots the subtree. // Set the new root of the subtree void remove( const C&x, BinaryNode* & t ) if( t nullptr ) if( x element) else if( t->element leftnullptr && t->rightnullptr) // Two children return; // Item not found; do nothing remove( x, t-left ); remove( x, t->right ); t-element-findMin( t->right )-element; remove( t->element, t->right ); else BinaryNode oldNodet; tt-left nullptr? t-left t->right; delete oldNode // Internal method to find the smallest item in a subtree t // Return node containing the smallest item BinaryNode* findMin( BinaryNode t) const if( t nullptr if( t->left nullptr ) return findMin( t-left); return nullptr; return t; //Internal method to find the largest item in a subtree t. // Return node containing the largest item. BinaryNode findMax( BinaryNode t const if( t nullptr while( t->right != nullptr ) t-t-right; return t; // Internal method to test if an item is in a subtree / x is item to search for, // t is the node that roots the subtree. bool contains const C& x, BinaryNode t ) const if( t nullptr ) else if( x element) else if( t->element left); return contains( x, t->right ); return true; // Match void makeEmpty( BinaryNode&t) if( t != nullptr ) makeEmpty( t->left); makeEmpty( t->right ); delete t; tnullptr; void printTree( BinaryNode t) const if( t !# nullptr ) printTree( t->left); cout element right); d: #endif Exercise 2: Program your own file lab87.cpp in which your main0 function will test the new data structure The main function is contained in the file labe7.cpp Declare an instance of BinarySearchTree (short: BST) suitable to hold integer values Prompt user to enter a random sequence of integer values, insert these values into the data structure (the entered values should NOT be in sorted order) Call the printTree() member function in order to print out the values of the BST structure . Prompt user to enter a random sequence of integer values, remove these values from your BST. Print out the reduced BST Exercise 3: Add the following member function in your BinarySearchTree class template public: void printInternal() print_Internal (root,0); private: void printInternal (BinaryNode t, int offset) if (tnullptr) return; for(int i 1; i (s offset ; i++) cout element right, offset 1); Go back to your program lab87.cpp and call printInternal. Compile and run your program, and see what you get. The expected result: insert the values (stop when entering 0): 10 5 20 3 22 6 18 79 13 15 4 2 1 19 30 8 0 print the values: 1-2 -3-4-5- 6- 7-8-9 1013 1518- 19 - 20 - 22- 30 Print the tree: 4 remove the values (stop when entering ): 1 11 2 12 3 13 0 print the values: 4-5- 6- 7- 8 - 9- 1015 18-19 - 20 - 22- 30 - Print the tree