Binary Search Tree Delete

  2. Tutorial
  3. Data Structure
  4. Binary Search Tree Delete
Harshit Jindal Oct 12, 2023
Data Structure Binary Tree Binary Search Tree
  1. Delete Operation on Binary Search Tree
  2. Binary Search Tree Delete Illustration
  3. BST Delete Algorithm
  4. Binary Search Tree Delete Implementation
  5. Binary Search Tree Delete Algorithm Complexity
Binary Search Tree Delete

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.

    Binary search tree delete operation
    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

    Binary search tree delete operation
    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.

    Binary search tree delete operation
    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 == NULL , then return NULL.
  • 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.
  • 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 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.

Author: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

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.

LinkedIn

Related Article - Data Structure

Related Article - Binary Tree

Related Article - Binary Search Tree