Binary Search Tree deletion of a node | BST operations

05 min read

The basic operations in a binary search tree are insertion and deletion operations. Program to delete a node from the binary search tree is given below.

 

Deletion in a Binary Search Tree

Given a binary search tree and data of the node to be deleted, delete the node in the binary search tree.

              bst deletion

 

Algorithm to delete a node in a Binary Search Tree

  • 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 to delete a node in a Binary Search Tree

#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;
}

 

Output:

binary search tree deletion

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error