C++

You will implement a binary search tree data structure in C++, and turn in a program evaluating the data structure. Implement a templated Binary Search Tree data structure, implementing the following functionality: Add(value to insert) Delete (delete given node, restructure sub-tree) Maximum(Find Maximum Key) To evaluate this data structure, write your program to read from an array of unsorted integers. You could also read from a data file (with the filename passed as a command line parameter) and populates the data structure. Rigorous testing is expected! Be sure to include tests for attempting to remove a node from an empty BST, attempting to insert a duplicate node, removing a node with no children, removing a node with one child, and removing a node with two children. Be sure to verify the BST organization and structure are correct.