C++ Program for binary search

For this assignment, you have been given the interface for a templated binary search tree class, and you must write the implementation. A binary search tree consists of a **root** node, which can have two children a*Left* and a *right* child. By convention, a binary search tree will uphold the **invariant** property that, for any node, all descendents of that node that are **less** than it will appear in its **left** branch, while all descendents that are **greater** than it will appear in its **right** branch. Thus, *binary search* can use this property to conduct search quickly (specifically, in $0(\log n)$ time). Algorithmically, this should be easier than Assignment 4; the new challenge will be dealing with **pointers** and writing code that follows chains of pointers You will also be writing a **templated class** In theory, it should support any type In practice, I will test your templated BST class by creating binary search trees containing the following data types int double std::string DNA