Delete a Node of BST
It is used to delete a node with specific key from the BST and return the new BST.
Different scenarios for deleting the node:
Node to be deleted is the leaf node :
Its simple you can just null it out.
Node to be deleted has one child :
You can just replace the node with the child node.
Node to be deleted has two child :
Here we have to delete the node is such a way, that the resulting tree follows the properties of a BST. The trick is to find the inorder successor of the node. Copy contents of the inorder successor to the node, and delete the inorder successor.
Take Care of following things while deleting a node of a BST:
- Need to figure out what will be the replacement of the node to be deleted.
- Want minimal disruption to the existing tree structure
- Can take the replacement node from the deleted nodes left or right subtree.
- If taking if from the left subtree, we have to take the largest value in the left subtree.
- If taking if from the right subtree, we have to take the smallest value in the right subtree.
Code:
Below is the implementation of the deletion in BST:
// C++ program to delete
// a node of BST
// Given Node node
struct node {
int key;
struct node *left, *right;
};
// Function to create a new BST node
struct node* newNode(int item)
{
struct node* temp
= (struct node*)malloc(
sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// Function to insert a new node with
// given key in BST
struct node* insert(struct node* node, int key)
{
// If the tree is empty, return a new node
if (node == NULL)
return newNode(key);
// Otherwise, recur down the tree
if (key < node->key) {
node->left = insert(node->left, key);
}
else if (key > node->key) {
node->right = insert(node->right, key);
}
// Return the node pointer
return node;
}
// Function that returns the node with minimum
// key value found in that tree
struct node* minValueNode(struct node* node)
{
struct node* current = node;
// Loop down to find the leftmost leaf
while (current && current->left != NULL)
current = current->left;
return current;
}
// Function that deletes the key and
// returns the new root
struct node* deleteNode(struct node* root,
int key)
{
// base Case
if (root == NULL)
return root;
// If the key to be deleted is
// smaller than the root's key,
// then it lies in left subtree
if (key < root->key) {
root->left
= deleteNode(root->left, key);
}
// If the key to be deleted is
// greater than the root's key,
// then it lies in right subtree
else if (key > root->key) {
root->right
= deleteNode(root->right, key);
}
// If key is same as root's key,
// then this is the node
// to be deleted
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:
// Get the inorder successor(smallest
// in the right subtree)
struct node* temp = minValueNode(root->right);
// Copy the inorder successor's
// content to this node
root->key = temp->key;
// Delete the inorder successor
root->right
= deleteNode(root->right, temp->key);
}
return root;
}
// C program to delete
// a node of BST
// Given Node node
struct node {
int key;
struct node *left, *right;
};
// Function to create a new BST node
struct node* newNode(int item)
{
struct node* temp
= (struct node*)malloc(
sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// Function to insert a new node with
// given key in BST
struct node* insert(struct node* node, int key)
{
// If the tree is empty, return a new node
if (node == NULL)
return newNode(key);
// Otherwise, recur down the tree
if (key < node->key) {
node->left = insert(node->left, key);
}
else if (key > node->key) {
node->right = insert(node->right, key);
}
// Return the node pointer
return node;
}
// Function that returns the node with minimum
// key value found in that tree
struct node* minValueNode(struct node* node)
{
struct node* current = node;
// Loop down to find the leftmost leaf
while (current && current->left != NULL)
current = current->left;
return current;
}
// Function that deletes the key and
// returns the new root
struct node* deleteNode(struct node* root,
int key)
{
// base Case
if (root == NULL)
return root;
// If the key to be deleted is
// smaller than the root's key,
// then it lies in left subtree
if (key < root->key) {
root->left
= deleteNode(root->left, key);
}
// If the key to be deleted is
// greater than the root's key,
// then it lies in right subtree
else if (key > root->key) {
root->right
= deleteNode(root->right, key);
}
// If key is same as root's key,
// then this is the node
// to be deleted
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:
// Get the inorder successor(smallest
// in the right subtree)
struct node* temp = minValueNode(root->right);
// Copy the inorder successor's
// content to this node
root->key = temp->key;
// Delete the inorder successor
root->right
= deleteNode(root->right, temp->key);
}
return root;
}
// Java program for Delete a Node of BST
class GFG {
// Given Node node
static class node {
int key;
node left, right;
};
// Function to create a new BST node
static node newNode(int item)
{
node temp = new node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// Function to insert a new node with
// given key in BST
static node insert(node node, int key)
{
// If the tree is empty, return a new node
if (node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < node.key) {
node.left = insert(node.left, key);
}
else if (key > node.key) {
node.right = insert(node.right, key);
}
// Return the node
return node;
}
// Function that returns the node with minimum
// key value found in that tree
static node minValueNode(node node)
{
node current = node;
// Loop down to find the leftmost leaf
while (current != null && current.left != null)
current = current.left;
return current;
}
// Function that deletes the key and
// returns the new root
static node deleteNode(node root, int key)
{
// base Case
if (root == null)
return root;
// If the key to be deleted is
// smaller than the root's key,
// then it lies in left subtree
if (key < root.key) {
root.left = deleteNode(root.left, key);
}
// If the key to be deleted is
// greater than the root's key,
// then it lies in right subtree
else if (key > root.key) {
root.right = deleteNode(root.right, key);
}
// If key is same as root's key,
// then this is the node
// to be deleted
else {
// Node with only one child
// or no child
if (root.left == null) {
node temp = root.right;
return temp;
}
else if (root.right == null) {
node temp = root.left;
return temp;
}
// Node with two children:
// Get the inorder successor(smallest
// in the right subtree)
node temp = minValueNode(root.right);
// Copy the inorder successor's
// content to this node
root.key = temp.key;
// Delete the inorder successor
root.right = deleteNode(root.right, temp.key);
}
return root;
}
# Python program to delete a node of BST
# Given Node node
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Function to insert a new node with
# given key in BST
def insert(root, key):
# If the tree is empty, return a new node
if root is None:
return Node(key)
# Otherwise, recur down the tree
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
# Return the node pointer
return root
# Function to do inorder traversal of BST
def inorder(root):
if root:
inorder(root.left)
print(root.key, end=" ")
inorder(root.right)
# Function that returns the node with minimum
# key value found in that tree
def minValueNode(node):
current = node
# Loop down to find the leftmost leaf
while current and current.left is not None:
current = current.left
return current
# Function that deletes the key and
# returns the new root
def deleteNode(root, key):
# base Case
if root is None:
return root
# If the key to be deleted is
# smaller than the root's key,
# then it lies in left subtree
if key < root.key:
root.left = deleteNode(root.left, key)
# If the key to be deleted is
# greater than the root's key,
# then it lies in right subtree
elif key > root.key:
root.right = deleteNode(root.right, key)
# If key is same as root's key,
# then this is the node
# to be deleted
else:
# Node with only one child
# or no child
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
# Node with two children:
# Get the inorder successor(smallest
# in the right subtree)
temp = minValueNode(root.right)
# Copy the inorder successor's
# content to this node
root.key = temp.key
# Delete the inorder successor
root.right = deleteNode(root.right, temp.key)
return root
Introduction to Binary Search Tree – Data Structure and Algorithm Tutorials
Binary Search Tree is a data structure used in computer science for organizing and storing data in a sorted manner. Binary search tree follows all properties of binary tree and its left child contains values less than the parent node and the right child contains values greater than the parent node. This hierarchical structure allows for efficient Searching, Insertion, and Deletion operations on the data stored in the tree.
Table of Content
- What is Binary Search Tree?
- Properties of Binary Search Tree
- Handling duplicate values in the Binary Search Tree
- Operations performed on a BST
- 1. Searching a node in BST
- 2. Insert a node into a BST
- 3. Delete a Node of BST
- 4. Traversal (Inorder traversal of BST)
- Applications of BST
- Advantages
- Disadvantages
- FAQ’s (Frequently asked questions) on Binary Search Tree: