# Binary Search Tree Delete

Harshit Jindal Oct 12, 2023

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.

Node `7` has no child; simply delete it from the tree, no BST property is violated.

• ##### The node to be deleted has only one child

Node `15` has one child `7`; we need to take care of it before deleting `15`. So, we copy it first and then replace it with `15`.

• ##### The node to be deleted has both children.

Node `21` has two children - `15` and `27`. We find the smallest element in the right subtree `23` and replace it with `21`, and then we call recursion to delete `23` from the right subtree.

## BST Delete Algorithm

• ##### If `root->key` < `X`, then discard the left subtree and find the element to be deleted in right subtree

`root->right` = `deleteNode(root->right,X)`

• ##### Else if `root->key` > `X`, then discard the right subtree and find the element to be deleted in left subtree

`root->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 delete `root` and return `NULL`.
• 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 subtree `minnode` and replace it with the node to be deleted. Recursively delete `minnode` from right subtree.

## 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 average-case, 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 best-case occurs when the tree is a balanced BST. The best-case time complexity of deletion is of the order of `O(logn)`. It is the same as average-case time complexity.

• Worst Case

In the worst-case, 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 worst-case 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.