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.

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.

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

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

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.

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.

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

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