Data Structures and Algorithms - Old Questions
1. Illustrate the algorithm for Binary search tree with example.
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
