A binary search tree is a hierarchical data structure which stores data in a non-linear fashion. It supports the insertion, search and deletion operations in O( log n ) time. Take a look at the below picture.
This is an example of binary search tree. The node at the top containing 5 is the root and all the elements to the left of it(left sub-tree) are less than 5 and all the elements to the right of it (right sub-tree) are greater than 5. A binary search tree does not allow duplicate elements in it.
In this post we see how an insertion method works. It works very similar to the binary search.
The insert method looks at the root. If the given data is lesser than root data, it has to be inserted into the left sub-tree. Otherwise it has to be added in the right sub-tree. Since the left/right sub-trees are also binary search trees, we call the procedure recursively.
Here is the complete C++ program which implements a binary search tree in Object Oriented approach. I have used in-order traversal to print all the elements of the binary search tree. These procedures are explained in future posts.