For this computer assignment, implement a derived class (as a template) to represent a binary search tree. Since a binary search tree is also a binary tree, implement your binary search tree class from the base class of binary trees, which you implemented in your previous assignment.

The definition of the derived class of a binary search tree (as a template) is given as follows:

template < class T >

class binSTree : public binTree < T > {

public:

void insert ( const T& x );

void remove ( const T& x );

private:

void insert ( Node < T >*&, const T& );

t void remove ( Node < T >*&, const T& );

Node < T >* pred ( Node < T >* );

Where x is the target value for insert ( ) and remove ( ) functions. These public functions simply call their private versions

The private versions of insert ( ) and remove ( ) functions can be implemented as recursive functions. When you implement the remove ( ) function, consider three possible cases: the node to be removed (1) is a leaf; (2) has only one child; and (3) has two children. In the first case, simply delete the node. In the second case, bypass the node making a new link from its parent to its child, and delete the node. In the third case, find the predecessor of the node first move to the left child of the node, and then move to rightmost node in the tree, replace the value of the node with the value of its predecessor, delete the predecessor, and update the link to the deleted node, where the private non-recursive member function pred ( ) can be used to return the predecessor of a node

To test your derived class, the source file of a driver program, prog7.cc, is supplied to you, which is in directory: ~cs340/progs/17f/p7. This program generates two sets of random integers in the range [ 0, R ] with R = 1000, and inserts these numbers of the first set in a vector of integers and the numbers of the second set in another vector of integers, and inserts the numbers of the first set in a binary search tree. The program searches for each number in the second vector in the binary search tree before and after the numbers in the second vector is removed from the tree. At the end, it prints the following values for the binary search tree: the number of nodes and the height of the tree. Finally, it prints the data values in the binary search tree in ascending order before and after the removals, since traversing a binary search tree inorder results a sorted list of values.

To get the size of a binary search tree, add the public and private versions of the size ( ) function in your binTree class with the prototypes unsigned size ( ) const and unsigned size ( Node < T >* ) const, respectively.

Put the implementation of your binary search tree class in a separate header file, say binSTree.h. Modified version of the class Node from the previous assignment includes the binTree and binSTree classes as friends, so the objects of these two classes can access the private members of the class Node. Include the header file Node.h in your header file binTree.h, and include the header file binTree.h in your header file binSTree.h. Make it sure that each header file is included only once, so the contents of each header file should be guarded as follows:

// include system header files

using namespace std;

#ifndef aconstvalue

#define aconstvalue

// statements in the header file

#endif