JIYIK CN >

In the article Binary Search Trees: Searching and Inserting , we discussed how to insert an element into a binary search tree and how to search for a value in a binary search tree. In this article, we will discuss how to delete a node from a binary search tree.

Deletion operation in binary search tree

Inserting a node into a binary search tree is relatively simple. However, when deleting a node, we must consider multiple possibilities. The following 3 situations may occur.

• The node to be deleted has no children and is a leaf node.

BST Delete Diagram

• The node to be deleted has no children, it is a leaf.

  
  Node 7has no children and can be simply deleted from the tree without violating the BST property.

• The node to be deleted has only one child.

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

• The node to be deleted has two children.

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

BST deletion algorithm

• If root== NULL, then return NULL.
• If root->key< X, then discard the left subtree and find the element to be deleted in the right subtree.

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

• Else If root->key> X, discard the right subtree and find the element to be removed in the left subtree.

  root->left= deleteNode(root->left, X).

• Else If root->key== X, then proceed according to three cases.
  • If ( root->left== NULLand root->right== NULL), remove rootand return NULL.
  • Otherwise if ( root->right== NULL), copy the left subtree and replace it with the node to be deleted.
  • Otherwise if ( root->left== NULL), copy the right subtree and replace it with the node to be deleted.
  • Else if ( root->left&& ), then find the smallest node in root->rightthe right subtree and replace it with the node to be deleted. Recursively delete from the right subtree .minnodeminnode
• Returns roota pointer to the original .

Binary search tree deletion 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);
}

Complexity of Binary Search Tree Deletion Algorithm

Time Complexity

• Average situation

On average, the time complexity of deleting a node from a BST is comparable to the height of the binary search tree. On average, the height of a BST is O(logn). This happens when the formed BST is a balanced BST. Therefore, the time complexity [Big Theta]: O(logn).

• Best Case

The best case is when the tree is a balanced BST. In the best case, the time complexity of deletion is O(logn). It is the same as the time complexity in the average case.

• Worst case scenario

In the worst case, we may need to go from the root node to the deepest leaf node, which is the entire height of the tree h. If the tree is unbalanced, i.e. it is skewed, the height of the tree may become n, so the worst case time complexity of insertion and search operations is O(n).

Space complexity

Due to the additional space required for the recursive calls, the space complexity of the algorithm is O(n).