Binary Search Tree Delete
 Delete Operation on Binary Search Tree
 Binary Search Tree Delete Illustration
 BST Delete Algorithm
 Binary Search Tree Delete Implementation
 Binary Search Tree Delete Algorithm Complexity
In the article Binary Search Tree: Search and Insert, we discussed how to insert an element in a BST and how to search for a value in a BST. In this article, we will discuss how to delete a node from the binary search tree.
Delete Operation on Binary Search Tree
Inserting a node in BST is relatively simple. But, while deleting a node we have to take care of multiple possibilities. Following 3 cases may occur:

The node to be deleted has no child  it is a leaf.
This is the simplest case; since a leaf node has no child, we do not need to care for anything. We can replace the leaf node with NULL
and free the space allocated to this node.

The node to be deleted has only one child (left or right child).
In this case, we store the node’s child and remove the node from its original position. The child node is then inserted at deleted node’s original position.

The node to be deleted has both children, left and right child.
This is the trickiest case because here, we can’t simply delete or replace the node with its child. In this case, we find the smallest node in the right subtree of node minnode
. Replace the node’s value to be deleted with minnode
’s value and recursively call delete on this node.
Binary Search Tree Delete Illustration

The node to be deleted has no child  it is a leaf.
Node7
has no child; simply delete it from the tree, no BST property is violated. 
The node to be deleted has only one child
Node15
has one child7
; we need to take care of it before deleting15
. So, we copy it first and then replace it with15
. 
The node to be deleted has both children.
Node21
has two children 15
and27
. We find the smallest element in the right subtree23
and replace it with21
, and then we call recursion to delete23
from the right subtree.
BST Delete Algorithm

If
root
==NULL
, then returnNULL
. 
If
root>key
<X
, then discard the left subtree and find the element to be deleted in right subtreeroot>right
=deleteNode(root>right,X)

Else if
root>key
>X
, then discard the right subtree and find the element to be deleted in left subtreeroot>left
=deleteNode(root>left, X)

Else if
root>key
==X
,then take action according to the 3 cases: If(
root>left
==NULL
&&root>right
==NULL
) then deleteroot
and returnNULL
.  Else if(
root>right
==NULL
) then copy the left subtree and replace it with the node to be deleted.  Else if(
root>left
==NULL
) then copy the right subtree and replace it with the node to be deleted.  Else if(
root>left
&&root>right
) then find the minimum node in right subtreeminnode
and replace it with the node to be deleted. Recursively deleteminnode
from right subtree.
 If(

Return the pointer to the original
root
.
Binary Search Tree Delete Implementation
#include <iostream>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node* newNode(int item) {
Node* temp = new Node;
temp>key = item;
temp>left = temp>right = NULL;
return temp;
}
void inorder(Node* root) {
if (root != NULL) {
inorder(root>left);
cout << root>key << " ";
inorder(root>right);
}
}
void insert(Node*& root, int key) {
Node* toinsert = newNode(key);
Node* curr = root;
Node* prev = NULL;
while (curr != NULL) {
prev = curr;
if (key < curr>key)
curr = curr>left;
else
curr = curr>right;
}
if (prev == NULL) {
prev = toinsert;
root = prev;
}
else if (key < prev>key) {
prev>left = toinsert;
}
else {
prev>right = toinsert;
}
}
Node* getmin(Node* root) {
Node* curr = root;
while (curr && curr>left) {
curr = curr>left;
}
return curr;
}
Node* deleteNode(Node* root, int key) {
if (root == NULL) return root;
if (key < root>key)
root>left = deleteNode(root>left, key);
else if (key > root>key)
root>right = deleteNode(root>right, key);
else {
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* temp = getmin(root>right);
root>key = temp>key;
root>right = deleteNode(root>right, temp>key);
}
return root;
}
int main() {
Node* root = NULL;
insert(root, 5);
insert(root, 3);
insert(root, 8);
insert(root, 6);
insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 7);
inorder(root);
cout << "\n";
deleteNode(root, 5);
inorder(root);
}
Binary Search Tree Delete Algorithm Complexity
Time Complexity
 Average Case
On averagecase, the time complexity of deleting a node from a BST is of the order of height of the binary search tree. On average, the height of a BST is O(logn)
. It occurs when the BST formed is a balanced BST. Hence the time complexity is of the order of [Big Theta]: O(logn)
.
 Best Case
The bestcase occurs when the tree is a balanced BST. The bestcase time complexity of deletion is of the order of O(logn)
. It is the same as averagecase time complexity.
 Worst Case
In the worstcase, we might have to traverse from root to the deepest leaf node i.e. the whole height h
of the tree. If the tree is unbalanced, i.e. it is skewed, the tree’s height may become n
, and hence the worstcase time complexity of both insert and search operation is O(n)
.
Space Complexity
The space complexity of the algorithm is O(n)
due to the extra space required by recursion calls.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedInRelated Article  Data Structure
 Circular Doubly Linked List
 Circular Linked List
 Doubly Linked List
 Linked List Deletion
 Linked List Insertion
 Linked List Merge Sort
Related Article  Binary Tree
 Convert Binary Tree to Binary Search Tree
 Binary Search Tree Check
 Binary Search Tree Inorder Succesor
 Binary Tree Traversal
 Binary Search Tree