Deletion In A Binary Search Tree

Deletion in a binary search tree removes a target node while preserving the tree’s defining order: every value in a node’s left subtree must be smaller than the node’s value, and every value in its right subtree must be larger. Unlike deleting from an array or linked list, deletion in a binary search tree must account for the node’s children and may require restructuring part of the tree.

This is the bit that actually matters in practice.

Introduction to Binary Search Tree Deletion

A binary search tree (BST) supports efficient searching, insertion, and deletion by organizing data hierarchically. For any node:

• All keys in its left subtree are less than its key.
• All keys in its right subtree are greater than its key.
• Both subtrees should also satisfy the binary search tree property.

When removing a value, it is not enough to disconnect the matching node. The remaining nodes must retain their correct relative order, and the parent of the deleted node must receive a valid replacement subtree. The appropriate technique depends on whether the target has zero, one, or two children.

The Three Deletion Cases

1. Deleting a Leaf Node

A leaf node has no children. This is the simplest case because removing it cannot disrupt the ordering of any remaining subtree Small thing, real impact..

For example:

    10
   /  \
  5    15

Deleting 5 only requires setting the corresponding child reference of 10 to null.

Result:

    10
      \
       15

No successor or child replacement is necessary.

2. Deleting a Node with One Child

If the target node has exactly one child, its parent can bypass it and connect directly to that child. This operation is often called splicing out the node.

Consider this tree:

      10
     /
    5
     \
      7

Deleting 5 means connecting 10 directly to 7 That alone is useful..

Result:

      10
     /
    7

The replacement works because the entire subtree rooted at 7 already satisfies the ordering requirements for its new position. If the deleted node is the root, its sole child simply becomes the new root Worth knowing..

3. Deleting a Node with Two Children

A node with two children cannot be removed and replaced by only one subtree without potentially violating the BST ordering rule. Instead, the usual algorithm replaces the node’s key with a value that can occupy its position legally.

There are two valid choices:

• The inorder successor: the smallest key in the right subtree.
• The inorder predecessor: the largest key in the left subtree.

The inorder successor is commonly used. Think about it: it is greater than every key in the deleted node’s left subtree and is the smallest key in its right subtree. Which means, placing it at the deleted node’s position preserves the BST property.

Suppose the tree is:

        8
      /   \
     3     10
    / \      \
   1   6      14
      / \    /
     4   7  13

To delete 3:

1. Find the minimum node in 3’s right subtree.
2. The successor is 4.
3. Copy 4 into the position currently occupied by 3.
4. Delete the original node containing 4.

The result is:

        8
      /   \
     4     10
    / \      \
   1   6      14
        \    /
         7  13

The original successor has no left child; otherwise, an even smaller value would exist in the right subtree. This means removing the successor becomes either the leaf case or the one-child case.

General Deletion Algorithm

A language-independent recursive implementation follows this pattern:

delete(root, key):
    if root is null:
        return null

    if key < root.key