Binary Search Tree Implementation in C++

Binary search tree(BST) is a kind of binary tree(tree where each node has at most 2 child nodes) where any node of the tree will be less than all its right children and greater than all its left children. For Instance

Binary search tree

To implement BST will implement three things that we can do on a BST:

1. Insertion
2. Search
3. Deletion

Insertion

If we want to insert a value in our BST, let’s say we want to insert 17 . We will start from the root node, which in our case has the value 12. So, We will compare 12 and 17, as 12 is less than 17 we will go the right of the tree. The right node has the value 15 which is less than 17, so we go to the right node which is 16. Again, 16 is less than 17, so we go to the right node. But there is no node to the right of 16 and we will insert 17 there.

Insertion in BST

Search

To search any values in BST, we will do exactly what we did for insertion. For example, to search 11, we will compare 11 to 12 which is greater than 11, so we will go to left node(i.e 6), which is less than 11 so we go to the right node(i.e. 7) , again 7 is less…