Deletion in Binary Search Tree (BST)
Given a BST, the task is to delete a node in this BST, which can be broken down into 3 scenarios:
Case 1. Delete a Leaf Node in BST
Case 2. Delete a Node with Single Child in BST
Deleting a single child node is also simple in BST. Copy the child to the node and delete the node.
Case 3. Delete a Node with Both Children in BST
Deleting a node with both children is not so simple. 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.
Note: Inorder predecessor can also be used.
Note: Inorder successor is needed only when the right child is not empty. In this particular case, the inorder successor can be obtained by finding the minimum value in the right child of the node.
Implementation of Deletion operation in a BST:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node *left, *right;
};
// A utility function to create a new BST node
Node* newNode(int item)
{
Node* temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to do inorder traversal of BST
void inorder(Node* root)
{
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
/* A utility function to insert a new node with given key in
* BST */
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
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
/* Given a binary search tree and a key, this function
deletes the key and returns the new root */
Node* deleteNode(Node* root, int k)
{
// Base case
if (root == NULL)
return root;
// If the key to be deleted is smaller than the root's key,
// then it lies in the left subtree
if (k < root->key) {
root->left = deleteNode(root->left, k);
return root;
}
// If the key to be deleted is greater than the root's key,
// then it lies in the right subtree
else if (k > root->key) {
root->right = deleteNode(root->right, k);
return root;
}
// If key is same as root's key, then this is the node to be deleted
// Node with only one child or no child
if (root->left == NULL) {
Node* temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL) {
Node* temp = root->left;
delete root;
return temp;
}
// Node with two children: Get the inorder successor (smallest
// in the right subtree)
Node* succParent = root;
Node* succ = root->right;
while (succ->left != NULL) {
succParent = succ;
succ = succ->left;
}
// Copy the inorder successor's content to this node
root->key = succ->key;
// Delete the inorder successor
if (succParent->left == succ)
succParent->left = succ->right;
else
succParent->right = succ->right;
delete succ;
return root;
}
// Driver Code
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
Node* root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
printf("Original BST: ");
inorder(root);
printf("\n\nDelete a Leaf Node: 20\n");
root = deleteNode(root, 20);
printf("Modified BST tree after deleting Leaf Node:\n");
inorder(root);
printf("\n\nDelete Node with single child: 70\n");
root = deleteNode(root, 70);
printf("Modified BST tree after deleting single child Node:\n");
inorder(root);
printf("\n\nDelete Node with both child: 50\n");
root = deleteNode(root, 50);
printf("Modified BST tree after deleting both child Node:\n");
inorder(root);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
struct Node *left, *right;
};
// A utility 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;
}
// A utility function to do inorder traversal of BST
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
/* A utility 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
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
/* Given a binary search tree and a key, this function deletes the key and returns the new root */
struct Node* deleteNode(struct Node* root, int k) {
// Base case
if (root == NULL)
return root;
// If the key to be deleted is smaller than the root's key, then it lies in the left subtree
if (k < root->key) {
root->left = deleteNode(root->left, k);
return root;
}
// If the key to be deleted is greater than the root's key, then it lies in the right subtree
else if (k > root->key) {
root->right = deleteNode(root->right, k);
return root;
}
// If key is same as root's key, then this is the node to be deleted
// 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* succParent = root;
struct Node* succ = root->right;
while (succ->left != NULL) {
succParent = succ;
succ = succ->left;
}
// Copy the inorder successor's content to this node
root->key = succ->key;
// Delete the inorder successor
if (succParent->left == succ)
succParent->left = succ->right;
else
succParent->right = succ->right;
free(succ);
return root;
}
// Driver Code
int main() {
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("Original BST: ");
inorder(root);
printf("\n\nDelete a Leaf Node: 20\n");
root = deleteNode(root, 20);
printf("Modified BST tree after deleting Leaf Node:\n");
inorder(root);
printf("\n\nDelete Node with single child: 70\n");
root = deleteNode(root, 70);
printf("Modified BST tree after deleting single child Node:\n");
inorder(root);
printf("\n\nDelete Node with both child: 50\n");
root = deleteNode(root, 50);
printf("Modified BST tree after deleting both child Node:\n");
inorder(root);
return 0;
}
class Node {
int key;
Node left, right;
Node(int item) {
key = item;
left = right = null;
}
}
class BinaryTree {
Node root;
BinaryTree() {
root = null;
}
// A utility function to insert a new node with the given key
Node insert(Node node, int key) {
// If the tree is empty, return a new node
if (node == null) {
return new Node(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 (unchanged) node pointer
return node;
}
// A utility function to do inorder traversal of BST
void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(root.key + " ");
inorder(root.right);
}
}
// Given a binary search tree and a key, this function deletes the key and returns the new root
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 the 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 the 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) {
return root.right;
} else if (root.right == null) {
return root.left;
}
// Node with two children: Get the inorder successor (smallest in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteNode(root.right, root.key);
}
return root;
}
int minValue(Node root) {
int minv = root.key;
while (root.left != null) {
minv = root.left.key;
root = root.left;
}
return minv;
}
// Driver Code
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.root = tree.insert(tree.root, 50);
tree.insert(tree.root, 30);
tree.insert(tree.root, 20);
tree.insert(tree.root, 40);
tree.insert(tree.root, 70);
tree.insert(tree.root, 60);
tree.insert(tree.root, 80);
System.out.print("Original BST: ");
tree.inorder(tree.root);
System.out.println();
System.out.println("\nDelete a Leaf Node: 20");
tree.root = tree.deleteNode(tree.root, 20);
System.out.print("Modified BST tree after deleting Leaf Node:\n");
tree.inorder(tree.root);
System.out.println();
System.out.println("\nDelete Node with single child: 70");
tree.root = tree.deleteNode(tree.root, 70);
System.out.print("Modified BST tree after deleting single child Node:\n");
tree.inorder(tree.root);
System.out.println();
System.out.println("\nDelete Node with both child: 50");
tree.root = tree.deleteNode(tree.root, 50);
System.out.print("Modified BST tree after deleting both child Node:\n");
tree.inorder(tree.root);
}
}
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
# A utility function to insert a new node with the given key
def insert(self, node, key):
# If the tree is empty, return a new node
if node is None:
return Node(key)
# Otherwise, recur down the tree
if key < node.key:
node.left = self.insert(node.left, key)
elif key > node.key:
node.right = self.insert(node.right, key)
# return the (unchanged) node pointer
return node
# A utility function to do inorder traversal of BST
def inorder(self, root):
if root:
self.inorder(root.left)
print(root.key, end=" ")
self.inorder(root.right)
# Given a binary search tree and a key, this function deletes the key and returns the new root
def deleteNode(self, 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 the left subtree
if key < root.key:
root.left = self.deleteNode(root.left, key)
# If the key to be deleted is greater than the root's key, then it lies in the right subtree
elif key > root.key:
root.right = self.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:
return root.right
elif root.right is None:
return root.left
# Node with two children: Get the inorder successor (smallest in the right subtree)
root.key = self.minValue(root.right)
# Delete the inorder successor
root.right = self.deleteNode(root.right, root.key)
return root
def minValue(self, root):
minv = root.key
while root.left:
minv = root.left.key
root = root.left
return minv
# Driver Code
if __name__ == "__main__":
tree = BinaryTree()
# Let us create following BST
# 50
# / \
# 30 70
# / \ / \
# 20 40 60 80
tree.root = tree.insert(tree.root, 50)
tree.insert(tree.root, 30)
tree.insert(tree.root, 20)
tree.insert(tree.root, 40)
tree.insert(tree.root, 70)
tree.insert(tree.root, 60)
tree.insert(tree.root, 80)
print("Original BST:", end=" ")
tree.inorder(tree.root)
print()
print("\nDelete a Leaf Node: 20")
tree.root = tree.deleteNode(tree.root, 20)
print("Modified BST tree after deleting Leaf Node:")
tree.inorder(tree.root)
print()
print("\nDelete Node with single child: 70")
tree.root = tree.deleteNode(tree.root, 70)
print("Modified BST tree after deleting single child Node:")
tree.inorder(tree.root)
print()
print("\nDelete Node with both child: 50")
tree.root = tree.deleteNode(tree.root, 50)
print("Modified BST tree after deleting both child Node:")
tree.inorder(tree.root)
using System;
public class Node {
public int key;
public Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
public class BinaryTree {
public Node root;
// A utility function to insert a new node with the given key
public Node Insert(Node node, int key) {
// If the tree is empty, return a new node
if (node == null)
return new Node(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 (unchanged) node pointer
return node;
}
// A utility function to do inorder traversal of BST
public void Inorder(Node root) {
if (root != null) {
Inorder(root.left);
Console.Write(root.key + " ");
Inorder(root.right);
}
}
// Given a binary search tree and a key, this function deletes the key and returns the new root
public 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 the 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 the 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)
return root.right;
else if (root.right == null)
return root.left;
// Node with two children: Get the inorder successor (smallest in the right subtree)
root.key = MinValue(root.right);
// Delete the inorder successor
root.right = DeleteNode(root.right, root.key);
}
return root;
}
public int MinValue(Node root) {
int minv = root.key;
while (root.left != null) {
minv = root.left.key;
root = root.left;
}
return minv;
}
// Driver Code
public static void Main(string[] args) {
BinaryTree tree = new BinaryTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.root = tree.Insert(tree.root, 50);
tree.Insert(tree.root, 30);
tree.Insert(tree.root, 20);
tree.Insert(tree.root, 40);
tree.Insert(tree.root, 70);
tree.Insert(tree.root, 60);
tree.Insert(tree.root, 80);
Console.Write("Original BST: ");
tree.Inorder(tree.root);
Console.WriteLine();
Console.WriteLine("\nDelete a Leaf Node: 20");
tree.root = tree.DeleteNode(tree.root, 20);
Console.Write("Modified BST tree after deleting Leaf Node:\n");
tree.Inorder(tree.root);
Console.WriteLine();
Console.WriteLine("\nDelete Node with single child: 70");
tree.root = tree.DeleteNode(tree.root, 70);
Console.Write("Modified BST tree after deleting single child Node:\n");
tree.Inorder(tree.root);
Console.WriteLine();
Console.WriteLine("\nDelete Node with both child: 50");
tree.root = tree.DeleteNode(tree.root, 50);
Console.Write("Modified BST tree after deleting both child Node:\n");
tree.Inorder(tree.root);
}
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
// A utility function to insert a new node with the given key
insert(node, key) {
// If the tree is empty, return a new node
if (node === null)
return new Node(key);
// Otherwise, recur down the tree
if (key < node.key)
node.left = this.insert(node.left, key);
else if (key > node.key)
node.right = this.insert(node.right, key);
// return the (unchanged) node pointer
return node;
}
// A utility function to do inorder traversal of BST
inorder(node) {
if (node !== null) {
this.inorder(node.left);
console.log(node.key + " ");
this.inorder(node.right);
}
}
// Given a binary search tree and a key, this function deletes the key and returns the new root
deleteNode(root, 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 the left subtree
if (key < root.key)
root.left = this.deleteNode(root.left, key);
// If the key to be deleted is greater than the root's key, then it lies in the right subtree
else if (key > root.key)
root.right = this.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)
return root.right;
else if (root.right === null)
return root.left;
// Node with two children: Get the inorder successor (smallest in the right subtree)
root.key = this.minValue(root.right);
// Delete the inorder successor
root.right = this.deleteNode(root.right, root.key);
}
return root;
}
minValue(node) {
let minv = node.key;
while (node.left !== null) {
minv = node.left.key;
node = node.left;
}
return minv;
}
}
// Driver Code
let tree = new BinaryTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.root = tree.insert(tree.root, 50);
tree.insert(tree.root, 30);
tree.insert(tree.root, 20);
tree.insert(tree.root, 40);
tree.insert(tree.root, 70);
tree.insert(tree.root, 60);
tree.insert(tree.root, 80);
console.log("Original BST:");
tree.inorder(tree.root);
console.log("\n\nDelete a Leaf Node: 20");
tree.root = tree.deleteNode(tree.root, 20);
console.log("Modified BST tree after deleting Leaf Node:");
tree.inorder(tree.root);
console.log("\n\nDelete Node with single child: 70");
tree.root = tree.deleteNode(tree.root, 70);
console.log("Modified BST tree after deleting single child Node:");
tree.inorder(tree.root);
console.log("\n\nDelete Node with both child: 50");
tree.root = tree.deleteNode(tree.root, 50);
console.log("Modified BST tree after deleting both child Node:");
tree.inorder(tree.root);
Output
Original BST: 20 30 40 50 60 70 Delete a Leaf Node: 20 Modified BST tree after deleting Leaf Node: 30 40 50 60 70 Delete Node with single child: 70 Modified BST tree after deleting single child No...
Time Complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(n).
Related Links: