How to Delete a Node from a Binary Search Tree?

A Binary Search Tree (BST) is a binary tree that satisfies the following requirements:

1. The value of a parent node is bigger than all values of its left sub tree.
2. The value of a parent node is smaller than all values of its right sub tree.

The following is an example of BST:

Binary Search Tree

If we want to delete a node from BST, we basically have 3 different situations:

Delete a leaf node

For example, if we want to delete 19 from the above BST example, we can just simply wipe out the link and reclaim the memory by deleting the node and making its parent pointing to NULL (cut the link and wipe out the memory).

The BST will still be valid after this node removed. The properties are still conserved.

Delete a node with only 1 child

It is clearly obvious that we can’t just delete/remove a node that is not a leaf node. Because we would abandon its sub tree as well. To delete a node with only 1 child, we can link its parent node to its only child.

For example, if we want to delete 7 in the above BST, we can link 5 to its only child 9, and remove the node 7. In other words, the sub tree of the to-be-deleted node will be re-attached and the properties of BST will be still valid.

Delete a node with 2 children

The most complex situation is to delete a node with 2 children.

bst-tree-example

If we want to delete 15 from the above BST, we can do some tricks to reduce the situation to either case 1 or case 2.

Find the Minimal value of its right subtree

If we find the minimal value of its right subtree, it should not be node with two children, otherwise the node’s left child will be smaller than 1. Given the above BST, the minimal value of 15’s subtree will be 17.

Then we replace the to-be-deleted value with 17, we then have two 17’s. So the next task is to delete the 17 from the original 15’s right sub tree. So this is the case of deleting node with only 1 children.

Why this works? Because the 17 is on the 15’s right subtree, so it should be greater than 15, which is also greater than any other nodes in the 15’s left subtree. 17 is also the minimal value in the 15’s right subtree, so 17 is less or equal than any of 15’s right sub tree. Of course we have a duplicate 17 after replacing 15 with the value 17.

Find the Maximum value of its left subtree

Similarly, we can find the maximum value of the to-be-deleted node’s left subtree and the proof/approach is similar. Another to note is that if the value found (either maximum or minimal) has no children, then we are reducing the case to case 1 where deleting a leaf node from a BST tree.

Example Source Code

We’ll use C++ to write recursion for the above 3 cases. To represent a tree, we use the following structure:

1
2
3
4
5

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};

Then the deletion function goes like this. To delete a node, we need to first locate it in the tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

struct Node* Delete(struct Node *root, int data) {
  if (root == NULL) {
     return NULL;
  }
  if (data < root->data) {  // data is in the left sub tree.
      root->left = Delete(root->left, data);
  } else if (data > root->data) { // data is in the right sub tree.
      root->right = Delete(root->right, data);
  } else {
     // case 1: no children
     if (root->left == NULL && root->right == NULL) {
        delete(root); // wipe out the memory, in C, use free function
        root = NULL;
     }
     // case 2: one child (right)
     else if (root->left == NULL) {
        struct Node *temp = root; // save current node as a backup
        root = root->right;
        delete temp;
     }
     // case 3: one child (left)
     else if (root->right == NULL) {
        struct Node *temp = root; // save current node as a backup
        root = root->left;
        delete temp;
     }
     // case 4: two children
     else {
        struct Node *temp = FindMin(root->right); // find minimal value of right sub tree
        root->data = temp->data; // duplicate the node
        root->right = Delete(root->right, temp->data); // delete the duplicate node
     }
  }
  return root; // parent node can update reference
}

struct Node* Delete(struct Node *root, int data) {
  if (root == NULL) {
     return NULL;
  }
  if (data < root->data) {  // data is in the left sub tree.
      root->left = Delete(root->left, data);
  } else if (data > root->data) { // data is in the right sub tree.
      root->right = Delete(root->right, data);
  } else {
     // case 1: no children
     if (root->left == NULL && root->right == NULL) {
        delete(root); // wipe out the memory, in C, use free function
        root = NULL;
     }
     // case 2: one child (right)
     else if (root->left == NULL) {
        struct Node *temp = root; // save current node as a backup
        root = root->right;
        delete temp;
     }
     // case 3: one child (left)
     else if (root->right == NULL) {
        struct Node *temp = root; // save current node as a backup
        root = root->left;
        delete temp;
     }
     // case 4: two children
     else {
        struct Node *temp = FindMin(root->right); // find minimal value of right sub tree
        root->data = temp->data; // duplicate the node
        root->right = Delete(root->right, temp->data); // delete the duplicate node
     }
  }
  return root; // parent node can update reference
}

The function returns the root node because the root may change after deletion. The FindMin function finds the minimal node of the given BST.

1
2
3
4
5
6
7
8
9

int FindMin(Node *root) {
   if (root == NULL) {
      return INT_MAX; // or undefined.
   }
   if (root->left != NULL) {
      return FindMin(root->left); // left tree is smaller
   }
   return root->data;
}

int FindMin(Node *root) {
   if (root == NULL) {
      return INT_MAX; // or undefined.
   }
   if (root->left != NULL) {
      return FindMin(root->left); // left tree is smaller
   }
   return root->data;
}

Right sub trees are always larger than the node, so we don’t need to travel the right sub trees in order to find the minimal value.

See also: Recursive Algorithm to Cut a Binary Search Tree (Remove Nodes Not In Range)

–EOF (The Ultimate Computing & Technology Blog) —