Technical Stuff

One of the complex operation on binary search tree is deleting a node. Insertion is easy by calling recursive insertion. But deletion wont work with recursive. We need to handle different cases for deletinga node. Lets see all possible cases one by one in detail.

Finding the node to delete: First step for deleting a node is to find the node in the tree. If the node is not in the tree, no need of delete. So below is the code snippet for finding the node.

current = root;
while(current!=NULL)
{
 if(current->info == key)
 {
 found = 1;
 break;
 }
 else
 {
 prev = current;
 if(current->info >= key)
 current = current->left;
 else
 current = current->right;
 }
}

Here we are maintaining two pointers prev and current, so that we can have the link to maintain. After finding the node to delete, there are four possible cases. See one by one.

Case1: Current node has zero child's as shown in below image. current node is either left or right child of the prev node.

we can simply remove the current node for the scenario which shown in the image. the code snippet is given below.

if((current->left == NULL) && (current->right == NULL))
{
 if(prev->left == current)
 prev->left = NULL;
 else
 prev->right = NULL;
 free(current);
}

Case2: Current node has one child either left or right.
Case2-A: Current node with right child as shown in the below image. There are two possibilities as shown in the below image.

See the sample code snippet below

if(current->left == NULL && current->right != NULL)
{
 if(prev->left == current)
 prev->left = current->right;
 else
 prev->right = current->right;
 free (current);
}

Case2-B: Current node with left child as shown in the below image. There are two possibilities as shown in the below image.
See the sample code snippet below.

if(current->right == NULL && current->left!=NULL)
{
 if(prev->left = current)
 prev->left = current->left;
 else
 prev->right = current->left;
 free(current);
}

Case 3: Current node with two child's as shown in the below image. There are again four possibilities as shown in the below images. These four cases we need to handle carefully.
Case3-A: If the current node right child has no children. The scenario is shown below.

We need to copy the tmp node data to current node and delete the tmp node.
Case3-B: If the current node has left child. This is the tricky one. If the left child is available (we can ignore whether right child is available or not), we need to find the smallest element in the left side and replace it with current node and delete the smallest node. To find the smallest element, just find the left most node from the tmp node. This is to satisfy the binary search tree property.
The sample code snippet is given below.
Case3-C: If the current node has only right child. The scenario is as shown in the image.
We need to copy the tmp data to current node and delete the tmp node. the code snippet is given below.

if(current->left != NULL && current->right != NULL)
{
 struct bst *tmp = current->right;
 //case3-A
 if(tmp->left == NULL && tmp->right == NULL)
 {
 current->info = tmp->info;
 //current = tmp;
 free(tmp);
 current->right = NULL;
 }
 //case3-B
 else if(current->right->left != NULL)
 {
 struct bst *left_current = current->right;
 struct bst *left_current_prev = current->right->left;
 while(left_current->left != NULL)
 {
 left_current_prev = left_current;
 left_current = left_current->left;
 }
 current->info = left_current->info;
 free(left_current);
 left_current_prev->left = NULL;
 }
 //case3-C
 else
 {
 struct bst *temp;
 temp = current->right;
 current->info = temp->info;
 current->right = temp->right;
 free(temp);
 }
}

Click here for the complete Binary search tree C program.

Labels: Binary Search Tree, Binary Tree, BST, Data Structures

In computer science Binary search tree or BST is one of most common data structure used. A Binary search tree is a binary tree which follow the below properties

• left sub tree of the node should contain less than or equal to node
• right sub tree of the node should contain the greater than to the node
• both left and right subtrees should also be a binary search tree

Binary search tree for the input values 8,13,3,11,1,6,14,12,4,7 is given below.



One of the most advantage of Binary search tree is , sorting and searching operations are very efficient. Worst case complexity of searching using BST method is O(log(n)) where n is no. of nodes. And worst case for sorting using BST is O(n), Where as traditional sorting algorithms like bubble sort or quick sort the worst case is O(n*n). In the average case for the sorting in BST, the complexity reduces to (log(n)).

Operations on Binary Search Tree:

• Searching
• inserting
• deleting
• sort
• traversal

Click here for complete working binary search tree C code.

Applications of the binary search tree:

• Dictionaries
• sets
• multi sets
• associate array

1 comment:

Labels: Binary Search Tree, Binary Tree, BST, Data Structures

Below is the complete working C code with all operations in Binary Search Tree.

#include<stdio.h>
#include<malloc.h>
struct bst
{
 int info;
 struct bst *left;
 struct bst *right;
};
void delete(struct bst *root, int key);
struct bst *find_min(struct bst *node);
struct bst *find_max(struct bst *node);
struct bst *insert(struct bst *node, int key);
void print_postorder(struct bst *root);
void print_preorder(struct bst *root);
void print_inorder(struct bst *root);
int height(struct bst *root);
//deleting the element which handles three cases
//1. deleting node has no leaf nodes
//2. deleting node has one child(left or right)
//3. deleting node has two childs
void delete(struct bst *root, int key)
{
 struct bst *current;
 struct bst *prev;
 int found = 0;
 if(root == NULL)
 {
 printf("The BST is empty\n");
 return;
 }
 current = root;
 while(current!=NULL)
 {
 if(current->info == key)
 {
 found = 1;
 break;
 }
 else
 {
 prev = current;
 if(current->info >= key)
 current = current->left;
 else
 current = current->right;
 }
 }
 if(!found)
 {
 printf("given key element is not in the BST\n");
 return;
 }
 //leaf node , no left n right childs
 if((current->left == NULL) && (current->right == NULL))
 {
 if(prev->left == current)
 prev->left = NULL;
 else
 prev->right = NULL;
 free(current);
 }
 //single child node (either left or right child)
 if(current->left == NULL && current->right != NULL)
 {
 if(prev->left == current)
 prev->left = current->right;
 else
 prev->right = current->right;
 free (current);
 }
 if(current->right == NULL && current->left!=NULL)
 {
 if(prev->left = current)
 prev->left = current->left;
 else
 prev->right = current->left;
 free(current);
 }
 // need to handle the very complex case(node with both left n right childs)
 if(current->left != NULL && current->right != NULL)
 {
 struct bst *tmp = current->right;
 if(tmp->left == NULL && tmp->right == NULL)
 {
 current->info = tmp->info;
 free(tmp);
 current->right = NULL;
 }
 else if(current->right->left != NULL)
 {
 struct bst *left_current = current->right;
 struct bst *left_current_prev = current->right->left;
 while(left_current->left != NULL)
 {
 left_current_prev = left_current;
 left_current = left_current->left;
 }
 current->info = left_current->info;
 free(left_current);
 left_current_prev->left = NULL;
 }
 else
 {
 struct bst *temp;
 temp = current->right;
 current->info = temp->info;
 current->right = temp->right;
 free(temp);
 }
 }
}
//finding the min value
struct bst *find_min(struct bst *node)
{
 if(node == NULL)
 return NULL;
 if(node->left == NULL)
 return node;
 else
 return find_min(node->left);
}
//finding the max value
struct bst *find_max(struct bst *node)
{
 if(node!=NULL)
 {
 while(node->right!=NULL)
 node = node->right;
 }
 return node;
}
//adding the new element to the BST
struct bst *insert(struct bst *node, int key)
{
 if(node == NULL)
 {
 //creating the new node with the key and left n right sub nodes empty
 node = (struct bst *)malloc(sizeof(struct bst));
 node->info = key;
 node->left = node->right = NULL;
 }
 else if(node->info >= key)
 node->left = insert(node->left, key);
 else
 node->right= insert(node->right, key);
 return node;
}
//printing post order (LRP)
void print_postorder(struct bst *root)
{
 struct bst *temp = root;
 if(temp!=NULL)
 {
 print_postorder(temp->left);
 print_postorder(temp->right);
 printf("%d ",temp->info);
 }
}
//printing preorder(PLR)
void print_preorder(struct bst *root)
{
 struct bst *temp = root;
 if(temp!=NULL)
 {
 printf("%d ",temp->info);
 print_preorder(temp->left);
 print_preorder(temp->right);
 }
}
//printing inorder (LPR)
void print_inorder(struct bst *root)
{
 struct bst *temp = root;
 if(temp!=NULL)
 {
 print_inorder(temp->left);
 printf("%d ",temp->info);
 print_inorder(temp->right);
 }
}
// to find the height of the tree
int height(struct bst *root)
{
 struct bst *temp = root;
 int leftH = 0;
 int rightH = 0;
 if(temp == NULL)
 return 0;
 if(temp->left)
 leftH = height(temp->left);
 if(temp->right)
 rightH = height(temp->right);
 return leftH >rightH ? leftH+1 : rightH+1;
}
int main()
{
 struct bst *root=NULL;
 struct bst *tmp=NULL;
 int i,n,key,option;
 printf("Enter the no. elements in the BST\n");
 scanf("%n",&n);
 printf("Enter the list of elements in the BST\n");
 for(i=0;i<n;i++)
 {
 scanf("%d",&key);
 root = insert(root,key);
 }
 printf("Below are the possible opetaions you can performe in the above created BST\n");
 printf("1. Insert\n2. Delete\n3. In-Order\n4. Pre-Order\n5. Post-Order\n6. Find Minimum\n7. Find Max\n8. height\n other value for exit");
 scanf("%d,&option");
 while(1)
 {
 switch(option)
 {
 case 1:
 printf("Enter the valeu to insert into the BST\n");
 scanf("%d",&key);
 root = insert(root,key);
 break;
 case 2:
 printf("Enter the value to delete from the BST\n");
 scanf("%d",&key);
 delete(root,key);
 break;
 case 3:
 print_inorder(root);
 break;
 case 4:
 print_preorder(root);
 break;
 case 5:
 print_postorder(root);
 break;
 case 6:
 if(tmp)
 printf("Min value in BST is %d\n",tmp->info);
 break;
 case 7:
 tmp = find_max(root);
 if(tmp)
 printf("Max value in BST is %d\n",tmp->info);
 break;
 case 8:
 printf("height of the BST is %d\n",height(root));
 break;
 default:
 return 0;
 break;
 }
 printf("Below are the possible opetaions you can performe in the above created BST\n");
 printf("1. Insert\n2. Delete\n3. In-Order\n4. Pre-Order\n5. Post-Order\n6. Find Minimum\n7. Find Max\n8. height\n other value for exit");
 scanf("%d,&option");
 }
}

Labels: Binary Search Tree, Binary Tree, BST, Data Structures