# Binary Search Tree deletion of a node | BST operations

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.

## 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 nodestruct 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 childif (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 noderoot->data = temp->data;// Delete the inorder successorroot->right = delete_node(root->right, temp->data);}return root;}// Function to do inorder traversal of BSTvoid 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 Functionint 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:

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`