A tree whose elements have at-most two children is called a Binary Tree.

Binary Search Tree is a node-based binary tree data structure which has the following properties:

The left subtree of a node contains only nodes with keys lesser than the nodes key.

The right subtree of a node contains only nodes with keys greater than the nodes key.

The left and right subtree each must also be a binary search tree.

Using the abstract Tree class, make a tree type class named BinarySearchTree having following functionalities:

void insertNode(Type) -> inserts a new node with a key of type Type in the Tree such that the property of BST is maintained.

bool search(Type) -> returns true if key of type Type is found in the binary search tree and false if the key isnt present.

Your program should be menu based and should ask the user what action he wishes to perform.

Note: Write constructor and destructor as well.