Binary Search Tree (BST) Operations

The following operations are performed on a binary search tree...
1.    Search
2.    Insertion
3.    Deletion

1) Search operation

Binary search trees are called “search trees” because they make searching for a certain value more efficient than in an unordered tree. In an ideal binary search tree, we do not have to visit every node when searching for a particular value.

Here is how we search in a binary search tree:

1. Read the search element from the user.
2. Compare the search element with the value of root node in the tree.
3. If both are matched, then display "Given node is found!!!" and terminate the function
4. If both are not matched, then check whether search element is smaller or larger than that node value.
5. If search element is smaller, then continue the search process in left subtree.
6. If search element is larger, then continue the search process in right subtree.
7. Repeat the same until we find the exact element or until the search element is compared with the leaf node
8. If we reach to the node having the value equal to the search value then display "Element is found" and terminate the function.
9. If we reach to the leaf node and if it is also not matched with the search element, then display "Element is not found" and terminate the function.

2) Inserting

New nodes in a binary search tree are always added at a leaf position. Performing a search can easily find the position for a new node.

3) Deleting

When removing from a binary search tree, we are concerned with keeping the rest of the tree in the correct order. This means removing is different depending on whether the node we are removing has children. There are three cases:

Case (1): If the node being removed is a leaf, it can simply be deleted.

          It is a simple case, of a node to be deleted has no children then just traverse to that node, keep track of  the parent node and decide in which side the node exist ( left or right) and set parent.left=NULL or parent.right=NULL.

Case (2): Node to be deleted has only one child

If the node has a single child, (left or right) we must move the child into the position of the node when deleting it.

Case (3): Node to be deleted has two children

If the node has two children, we must first find the In-Order Predecessor (IOP): the largest node in our node’s left subtree. The IOP is always a leaf node, and can be found by starting at the left subtree’s root and moving right. We can then swap the node being removed with its IOP and delete it, as it is now a leaf. One can also swap the root with In-Order Successor(IOS)