Definition: A binary tree is said to be a binary search tree if it is the empty tree or

1. if there is a left-child, then the data in the left-child is less than the data in the root,
2. if there is a right-child, then the data in the right-child is no less than the data in the root, and every sub-tree is a binary search tree. // algorithm to implement insertion operation in BST

Insertion in Binary Search Tree:

• Check whether root node is present or not(tree available or not). If root is NULL, create root node.
• If the element to be inserted is less than the element present in the root node, traverse the left sub-tree recursively until we reach T->left/T->right is NULL and place the new node at T->left(key in new node < key in T)/T->right (key in new node > key in T).
• If the element to be inserted is greater than the element present in root node, traverse the right sub-tree recursively until we reach T->left/T->right is NULL and place the new node at T->left/T->right.

Algorithm for insertion in Binary Search Tree:

TreeNode insert(int data, TreeNode T) {
          if T is NULL {
                  T = (TreeNode *)malloc(sizeof (Struct TreeNode));
                  (Allocate Memory of new node and load the data into it)
                  T->data = data;
                  T->left   = NULL;
                  T->right = NULL;
          } else if T is less than T->left {
                  T->left = insert(data, T->left);
                  (Then node needs to be inserted in left sub-tree.So, 
                    recursively traverse left sub-tree to find the place 
                    where the new node needs to be inserted)
          } else if T is greater than T->right {
                   T->right = insert(data, T->right);
                   (Then node needs to be inserted in right sub-tree
                    So, recursively traverse right sub-tree to find the 
                     place where the new node needs to be inserted.)
         }
         return T;
}
// algorithm for implementing the delete operation in BST

Delete operation on binary search tree is more complicated, then add and search. Basically, in can be divided into two stages:

• search for a node to delete;
• if the node is found, run delete algorithm.

Delete algorithm in detail:

Now, let's see more detailed description of a remove algorithm. First stage is identical to algorithm for lookup, except we should track the parent of the current node. Second part is trickier. There are three cases, which are described below.

1. Node to be deleted has no children.

   This case is quite simple. Algorithm sets corresponding link of the parent to NULL and disposes the node. Example. Remove -4 from a BST.

1. Node to be deleted has one child.

   It this case, node is cut from the tree and algorithm links single child (with it's subtree) directly to the parent of the removed node. Example. Remove 18 from a BST.

1. Node to be deleted has two children.

   This is the most complex case. To solve it, let us see one useful BST property first. We are going to use the idea, that the same set of values may be represented as different binary-search trees. For example those BSTs:

contains the same values {5, 19, 21, 25}. To transform first tree into second one, we can do following:

• choose minimum element from the right subtree (19 in the example);
• replace 5 by 19;
• hang 5 as a left child.

The same approach can be utilized to remove a node, which has two children:

• replace value of the node to be removed with found minimum. Now, right subtree contains a duplicate!
• apply remove to the right subtree to remove a duplicate.