# Binary Search Tree (BST) with algorithm and implementation

Share

A binary search tree (BST) is an ordered or sorted binary tree in which all the keys in the left sub-tree of the root are smaller than the keys in the root node and all the keys in the right sub-tree of the root are greater than the keys in the root node. The left and right sub-tree of the root are again binary search trees.

## Operation on binary search Tree:

1. search (K,T) : search for key k in the tree T . If k is found in some node of the tree then return true otherwise return false.
2. insert (K,T) : Insert a new node with value k in the info field in the tree T such that the property of the BST is maintained.
3. Delete (K,T) : Delete a node with value k in the info field from the tree T such that the property of BST is maintaiined.
4. Findmin(T),FIndmax(T) : Find minimum and maximum element from the given non-empty BST.

## Algorithm for insertion in Binary Search Tree (BST).

• Search (root, item)
• Step 1 – if (item = root → data) or (root = NULL)
• return root.
• else if (item < root → data)
• return Search(root → left, item)
• else.
• return Search(root → right, item)
• END if.

## Program for the insertion in BST.

``````#include<stdio.h>
#include<stdlib.h>
void insert(int);
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *root;
void main ()
{
int choice,item;
do
{
printf("\nEnter the item which you want to insert?\n");
scanf("%d",&item);
insert(item);
printf("\nPress 0 to insert more ?\n");
scanf("%d",&choice);
}while(choice == 0);
}
void insert(int item)
{
struct node *ptr, *parentptr , *nodeptr;
ptr = (struct node *) malloc(sizeof (struct node));
if(ptr == NULL)
{
printf("can't insert");
}
else
{
ptr -> data = item;
ptr -> left = NULL;
ptr -> right = NULL;
if(root == NULL)
{
root = ptr;
root -> left = NULL;
root -> right = NULL;
}
else
{
parentptr = NULL;
nodeptr = root;
while(nodeptr != NULL)
{
parentptr = nodeptr;
if(item < nodeptr->data)
{
nodeptr = nodeptr -> left;
}
else
{
nodeptr = nodeptr -> right;
}
}
if(item < parentptr -> data)
{
parentptr -> left = ptr;
}
else
{
parentptr -> right = ptr;
}
}
printf("Node Inserted");
}
}  ``````
```         100                               100
/   \        Insert 40            /    \
20     500    --------->          20     500
/  \                              /  \
10   30                           10   30
\
40```

## Algorithm for deletion In BST.

• Input the number of nodes.
• Input the nodes of the tree.
• Consider the first element as the root element and insert all the elements.
• Input the data of the node to be deleted.
• If the node is a leaf node, delete the node directly.
• Else if the node has one child, copy the child to the node to be deleted and delete the child node.
• Else if the node has two children, find the inorder successor of the node.
• Copy the contents of the inorder successor to the node to be deleted and delete the inorder successor.

## program for deletion in BST.

```#include<stdio.h>
#include<stdlib.h>

/* Structure of the node */
struct node
{
int data;
struct node *left, *right;
}*root;

// Function to create a new node
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}

/* Function to find the minimum value node */
struct node * minValueNode(struct node* node)
{
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}

/* Function to delete the given node */
struct node* delete_node(struct node* root, int data)
{
if (root == NULL)
return root;
// If the key to be deleted is smaller than the root's key,
if (data < root->data)
root->left = delete_node(root->left, data);
// If the key to be deleted is greater than the root's key,
else if (data > root->data)
root->right = delete_node(root->right, data);
else
{
// node with only one child or no child
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
// node with two children:
struct node* temp = minValueNode(root->right);
// Copy the inorder successor's content to this node
root->data = temp->data;
// Delete the inorder successor
root->right = delete_node(root->right, temp->data);
}
return root;
}

// Function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

/* Function to insert a new node with given key in BST */
struct node* insert(struct node* node, int data)
{
/* If the tree is empty, return a new node */
if (node == NULL)
return newNode(data);
/* Recur down the tree */
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
return node;
}

// Main Function
int main()
{
int n;
root = NULL;
printf("\nEnter the number of nodes : ");
scanf("%d", &n);
int i;
int data;
printf("\nInput the nodes of the binary search tree : ");
if(n > 0)
{
scanf("%d", &data);
root = insert(root, data);
}
for(i = 1; i < n; i++)
{
scanf("%d", &data);
insert(root, data);
}
printf("\nInorder traversal of the BST : ");
inorder(root);
printf("\n");
int del_ele;
printf("\nEnter the node to be deleted : ");
scanf("%d", &del_ele);
delete_node(root, del_ele);
printf("\nInorder traversal after deletion : ");
inorder(root);
printf("\n");
return 0;
}
```
Share