Deleting Nodes in a BST

Deleting a node from a binary search tree (BST) is a fundamental operation that must preserve the tree's sorted order and structural integrity. A naive removal would leave a gap, breaking the links and invalidating the BST properties.

The Challenge of Deletion

When a node is removed, its parent's link to it, and its children's links from it, are broken. The primary challenge is to patch this gap by rearranging the remaining nodes such that the BST rules (left child < parent < right child) are still upheld throughout the tree.

Case 1: Deleting a Leaf Node

This is the simplest scenario. A leaf node has no children. To delete it, you simply remove the node and update its parent's pointer to `null`. No further restructuring is needed because no children need to be reconnected.

Case 2: Deleting a Node with One Child

If the node to be deleted has only one child (either left or right), the process is straightforward. The child node effectively takes the place of the deleted node. The parent of the deleted node is re-linked to point directly to the deleted node's child, and the child's parent pointer is updated accordingly. This promotes the single child to its parent's spot.

Case 3: Deleting a Node with Two Children

This is the most complex case because two children are competing for the deleted node's position. To maintain the BST property, we must find a replacement that is greater than all nodes in the left subtree and smaller than all nodes in the right subtree. The standard approach is to find the *inorder successor*.

Finding the Inorder Successor

The inorder successor is the smallest node in the deleted node's right subtree. To find it, you traverse once to the right child of the node to be deleted, then continuously traverse left until you reach a node with no left child. This node is the inorder successor.

Performing the Deletion

Once the inorder successor is found, its value is copied into the node targeted for deletion. Then, the inorder successor node itself is deleted from its original position. Since the inorder successor will either be a leaf node or have at most one right child (it cannot have a left child by definition of being the smallest in its subtree), its deletion can be handled by Case 1 or Case 2, simplifying the overall process.

function deleteNode(root, key):
  if root is null, return null

  if key < root.value:
    root.left = deleteNode(root.left, key)
  else if key > root.value:
    root.right = deleteNode(root.right, key)
  else: // key is same as root.value, this is the node to be deleted
    if root.left is null: return root.right // Case 2 or Case 1 (if root.right is also null)
    else if root.right is null: return root.left // Case 2
    else: // Case 3: Node with two children
      successor = findMin(root.right) // Find inorder successor
      root.value = successor.value // Copy successor's value
      root.right = deleteNode(root.right, successor.value) // Delete the successor from its original spot

  return root

function findMin(node):
  while node.left is not null:
    node = node.left
  return node

Key Takeaways

• Deleting a node in a BST requires careful handling to preserve its properties.
• Leaf nodes are the simplest to remove, requiring no complex restructuring.
• Nodes with one child are removed by promoting their single child.
• Nodes with two children are handled by finding their inorder successor, copying its value, and then deleting the successor from its original position.