Exercise 1: Implement the BinarySearchTree ADT in a file BinarySearchTree.h exactly as shown below. // BinarySearchTree.h // after Mark A. Weiss, Chapter 4, Dr. Kerstin Voigt #ifndef BINARY SEARCH TREE H #define BINARY SEARCH TREE H #include assert> #include using namespace std; template class BinarySearchTree public: BinarySearchTree) root nullptr BinarySearchTree() makeEmpty(); const C& findMin() const assert (!isEmpty()); return findMin( root )->element; const C & findMax const assert (!isEmpty()); return findMax root )-element bool contains( const C & x) const return contains( x, root); // Internal method to insert into a subtree // x is the item to insert. // t is the node that roots the subtree // Set the new root of the subtree. void insert( const C&x, BinaryNode& t) if( t- nullptr) else if( x element) else if( t->element left; insert( x, t->right ); ; /1 Duplicate; do nothing else // 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 x ) else if t->left- nullptr && t->right nullptr)// 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; t ( t->left != nullptr ) ? t-left : t-right ; delete oldNode; void printTree BinaryNode* t) const if t nullptr) printTree( t >left) cout element right); 3; #endif Exercise 2: Program your own file labe7.cpp in which your main function will test the new data structure The main function is contained in the file lab07.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,e); private: void printInternal(BinaryNode* t, int offset) if (t nullptr) return; for(int i - 1; i element left, offset 1); print!nternal(t-right, offset + 1); The expected result insert the values (stop when entering 0): 10 5 20 3 22 6 18 79 13 15 4 2 119 30 8 0 print the values: 1-2 - 3- 45-6 - 7- 8-9 -10 - 13- 15- 18 -19 2022 30 Print the tree: 10 remove the values (stop when entering 0): 1 11 2 12 3 13 0 print the values: 4-5 -67- 8-9 - 10 15 -18-19-20-22 30 Print the tree: 10 4 6 $g++ -c BinarySearchTree.h $g++ -c lab07.cpp $./1ab7 Exercise 1: Implement the BinarySearchTree ADT in a file BinarySearchTree.h exactly as shown below. // BinarySearchTree.h // after Mark A. Weiss, Chapter 4, Dr. Kerstin Voigt #ifndef BINARY SEARCH TREE H #define BINARY SEARCH TREE H #include assert> #include using namespace std; template class BinarySearchTree public: BinarySearchTree) root nullptr BinarySearchTree() makeEmpty(); const C& findMin() const assert (!isEmpty()); return findMin( root )->element; const C & findMax const assert (!isEmpty()); return findMax root )-element bool contains( const C & x) const return contains( x, root); // Internal method to insert into a subtree // x is the item to insert. // t is the node that roots the subtree // Set the new root of the subtree. void insert( const C&x, BinaryNode& t) if( t- nullptr) else if( x element) else if( t->element left; insert( x, t->right ); ; /1 Duplicate; do nothing else // 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 x ) else if t->left- nullptr && t->right nullptr)// 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; t ( t->left != nullptr ) ? t-left : t-right ; delete oldNode; void printTree BinaryNode* t) const if t nullptr) printTree( t >left) cout element right); 3; #endif Exercise 2: Program your own file labe7.cpp in which your main function will test the new data structure The main function is contained in the file lab07.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,e); private: void printInternal(BinaryNode* t, int offset) if (t nullptr) return; for(int i - 1; i element left, offset 1); print!nternal(t-right, offset + 1); The expected result insert the values (stop when entering 0): 10 5 20 3 22 6 18 79 13 15 4 2 119 30 8 0 print the values: 1-2 - 3- 45-6 - 7- 8-9 -10 - 13- 15- 18 -19 2022 30 Print the tree: 10 remove the values (stop when entering 0): 1 11 2 12 3 13 0 print the values: 4-5 -67- 8-9 - 10 15 -18-19-20-22 30 Print the tree: 10 4 6 $g++ -c BinarySearchTree.h $g++ -c lab07.cpp $./1ab7