Deleting a Node in a BST

Deleting a node from a binary search tree (BST) is a crucial operation that must maintain the tree's structural integrity and the BST property. Improper deletion can corrupt the tree, leading to incorrect search results.

Why Deleting Nodes is Complex

Unlike simply removing an element from an array, deleting a node in a BST requires careful handling because the node might have children. Removing it directly could orphan its descendants or break the ordered structure of the tree. There are three distinct cases to consider, each with its own strategy.

Case 1: Deleting a Leaf Node

The simplest scenario is when the node to be deleted is a leaf node, meaning it has no children. In this case, the node can be directly removed without affecting any other part of the tree. The parent's pointer to this node is simply set to null.

Case 2: Deleting a Node with One Child

If the node to be deleted has only one child (either left or right), the process involves bypassing the node. The node's parent is made to point directly to the node's single child. This effectively removes the node while keeping its child connected to the tree in the correct position.

Case 3: Deleting a Node with Two Children

This is the most complex case. When a node with two children is deleted, it must be replaced by another node to maintain the BST property. The ideal replacement is the node's *in-order successor*.

Finding the In-Order Successor

The in-order successor of a node is the smallest value in its right subtree. To find it, you traverse to the right child of the node to be deleted, and then continuously move to the left child until no more left children exist. This successor node is guaranteed to have at most one child (a right child).

Replacement Process

Once the in-order successor is found, its value is copied into the node that is being deleted. After this value swap, the original in-order successor node (which is now a duplicate and at most has one child) is then deleted using either Case 1 or Case 2 logic. This two-step process ensures the BST property is preserved.

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

  if key < root.value:
    root.left = deleteNode(root.left, key)
  else if key > root.value:
    root.right = deleteNode(root.right, key)
  else: // Node with key found
    // Case 1: No child or Case 2: One child
    if root.left is null:
      return root.right
    else if root.right is null:
      return root.left
    
    // Case 3: Two children
    successor = findMin(root.right)
    root.value = successor.value
    root.right = deleteNode(root.right, successor.value)
  
  return root

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

Key takeaways

• Deleting a node in a BST requires handling three distinct cases to preserve tree integrity.
• Leaf nodes are deleted directly by setting the parent's pointer to null.
• Nodes with one child are deleted by bypassing them, connecting the parent directly to the child.
• Nodes with two children require finding their in-order successor.
• The in-order successor's value replaces the deleted node's value, and then the successor node is deleted from its original position.