# Illustrate the algorithm for Binary search tree with example.

Your limit has been exceed. We have implemented this system because, We got difficulty on managing our servers. Please donate some amount to remove this limit.

Quota: 0 / 30

Binary Search Tree

A binary search tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions:

• All keys in the left sub-tree of the root are smaller than the key in the root node
• All keys in the right sub-tree of the root are greater than the key in the root node
•  The left and right sub-trees of the root are again binary search trees

Example:

Given the following sequence of numbers,

14, 4, 15, 3, 9, 14, 18

The following binary search tree can be constructed:

Algorithm to search the element in BST

void BinSearch(struct bnode *root , int key)
{
if(root == NULL)
{
printf(“The number does not exist”);
exit(1);
}
else if (key == root->info)
{
printf(“The searched item is found”):
}

else if(key < root->info)
return BinSearch(root->left, key);
else
return BinSearch(root->right, key);

}

Algorithm to insert the element in BST

void insert(struct bnode *root, int item)
{
if(root=NULL)
{
root=(struct bnode*)malloc (sizeof(struct bnode));
root->left=root->right=NULL;
root->info=item;
}
else
{
if(item<root->info)
root->left=insert(root->left, item);
else
root->right=insert(root->right, item);
}
}

E.g.

Algorithm to delete the element in BST

struct bnode *delete(struct bnode *root, int item)
{
struct bnode *temp;

if(root==NULL)
{
printf(“Empty tree”);
return;
}
else if(item<root->info)
root->left=delete(root->left, item);
else if(item>root->info)
root->right=delete(root->right, item);
else if(root->left!=NULL &&root->right!=NULL)   //node has two child
{
temp=find_min(root->right);
root->info=temp->info;
root->right=delete(root->right, root->info);
}
else
{
temp=root;
if(root->left==NULL)
root=root->right;
else if(root->right==NULL)
root=root->left;
free(temp);
}
return(temp);
}

Finding minimum element function:

struct bnode *find_min(struct bnode *root)
{
if(root==NULL)
return0;
else if(root->left==NULL)
return root;
else
return(find_min(root->left));
}

E.g.

1.Deleting leaf Node

2.Deleting node with right child

3.Deleting node with left child

4.Deleting a node having both right and left child