Binary Search Tree Algorithm in Data Structure

Binary Search Tree:

A binary search tree is a binary tree in which each node has a value greater than every node of its left sub-tree and less than every node of its right sub-tree. This type of tree does not contain a duplicate value. The in-order traversal of the binary search tree gives a list in ascending order.

Binary Search Tree Algorithm in Data Structure

Insertion into Binary Search Tree:

Consider the following items:
ITEMS:   M      F      P      B      I      Q

We have to create a binary search tree using the items.

Solutions:
Step1: The first item in the list is M. As the tree is empty, insert M as the root node.

Binary Search Tree Algorithm in Data Structure

Step2: The second item F is less than the root M. So insert F as the left child of M.

Binary Search Tree Algorithm in Data Structure

Step3: Next item P is greater than M, So insert P as the right child of M.

Binary Search Tree Algorithm in Data Structure

Step4: Next item in the list is B. It is less than root M. So the next comparison takes place with F (the left child of M). Now B is less than F and the left child of F is NULL. So insert B as the left child of F.

Binary Search Tree Algorithm in Data Structure

Step5: Next item I is less than the root M and greater than F (left child of M). As the right child of F is NULL, insert I as the right child of F.

Binary Search Tree Algorithm in Data Structure

Step6: The last item Q is greater than the root M and its child P. So insert Q as the right child of P.

Binary Search Tree Algorithm in Data Structure

Algorithm for Insertion into Binary Search Tree:

{
 Algorithm fnInsertBST(iData)
{
  TreeNode *ptrNewNode, *ptrParent, *ptrChild;
  ptrNewNode=(Treenode *)malloc(sizeof(TreeNode));
  ptrNewNode->ptrLeft=ptrNewNode->ptrRight=NULL;
  ptrNewNode->info=iData;
  if(ptrRoot==NULL)
  {
    ptrRoot=ptrNewNode;
  else
  {
    ptrChild=ptrRoot;
    while(ptrChild!=NULL)
    {
      ptrParent=ptrChild;
      if(ptrChild->info>iData)
         ptrChild=ptrChild->ptrLeft;
      else if(ptrChild->info<iData)
         ptrChild=ptrChild->ptrRight;
      else
         return 0;
    }
    if(ptrParent->info>iData)
       ptrParent->ptrLeft=ptrNewNode;
    else
       ptrParent->ptrRight=ptrNewNode;
   }
   return 1;
}   // End of Algorithm

Recursive Algorithm for insertion into Binary Search Tree:

Algorithm TreeNode *fnInsert_BST(ptrRoot, iData)
{
  if(ptrRoot==Null)
  {
    ptrRoot=(TreeNode *) malloc(sizeof(TreeNode));
    ptrRoot ->ptrLeft=NULL;
    ptrRoot ->ptrRight=NULL;
    ptrRoot ->info=iData;
  }
elseif(iData < iData< ptrRoot ->info)
ptrRoot->ptrLeft=fnInsert_BST(ptrRoot->ptrLeft, iData);
elseif(iData>ptrRoot->info)
ptrRoot->ptrRight=fnInsert_BST(ptrRoot->ptrRight, iData);
else
 print(Duplicate node);
return(ptrRoot);
}  // End of Algorithm

Deletion from Binary Search Tree:

Rules:
1. If the node has no child then simply remove it.

2. If the node has one child then moves up to the only child.

3. If the node has two children then replace its position with its in-order successor or predecessor.

Algorithm to Delete a Node from a Binary Search Tree:

Algorithm fnDelete_BST(ptrDeleteNode)
{
  if(ptrDeleteNode->ptrLeft==NULL && ptrDeleteNode->ptrRight==NULL)
  {
    free(ptrDeleteNode);
    return;
  }
else if(ptrDeleteNode->ptrLeft!=NULL && ptrDeleteNode->ptrRight!=NULL)
{
  ptrSuccessor = Get_Inorder_Successor(ptrDeleteNode);
  ptrSuccessor->ptrLeft=ptrDeleteNode->ptrLeft;
  ptrSuccessor->ptrRight=ptrDeleteNode->ptrRight;
  free(ptrDeleteNode);
  return;
}
else if(ptrDeleteNode->ptrLeft==NULL && ptrDeleteNode->ptrRight!=NULL)
{
  ptrParent==Get_Parent(ptrDeleteNode);
 if(ptrParent->ptrLeft==ptrDeleteNode)
   ptrParent->ptrLeft=ptrDeleteNode->ptrRight;
 else
   ptrParent->ptrRight=ptrDeleteNode->ptrRight;
 free(ptrDeleteNode);
 return;
}
else
{
  ptrParent=Get_Parent(ptrDeleteNode);
 if(ptrParent->ptrLeft==ptrDeleteNode)
  ptrParent->ptrLeft=ptrDeleteNode->ptrLeft;
 else
  ptrParent->ptrRight=ptrDeleteNode-ptrLeft;
 free(ptrDeleteNode);
 return;
}
} // End of Algorithm