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;
}
Lightbox
Share
%d bloggers like this: