How do you write c plus plus program to insert an element into a binary search tree?

Binary Search is an algorithm that finds an element by successively halving the search space. Typically, pointers are used, one for the beginning of an array, one for the end. Then a midpoint pointer is chosen, and a test is performed. You either find the element, or you discover that the target element is before or after the midpoint. You then adjust either the start pointer or the end pointer and you iterate. When you reach the point where the pointers are out of order, you conclude that the target is not found, and you also know where to insert it. Binary Search is best implemented with an ordered array, because you want to make "random" access to each element. The problem with arrays is that they are typically fixed size, and must be dynamically adjusted when they need to grow, a potentially "expensive" operation. You can also implement a Binary Tree, but there is cost in development and processing. Even trees have issues because, when inserting and deleting elements, you must use a rebalancing algorithm, otherwise the tree might degrade to a linked list, which is not efficient when used as a search space. In C++, it is possible to declare and define a class of elements that you can add to, subtract from, and search. If you do this correctly, you could start with a static or dynamic array, and then upgrade if need be to a binary tree, and then upgrade if need be to a balanced binary tree, all the while without requiring change to the public interface. That is perhaps the most important value of an Object Oriented Language such as C++.