Delete Operation in Binary Search Trees

Understanding the Delete Operation

Deletion in a binary search tree (BST) is more complex than insertion or search because removing a node requires restructuring the tree to maintain the BST property. There are three cases to consider:

1. Deleting a leaf node (a node with no children)
2. Deleting a node with one child
3. Deleting a node with two children

Deletion Algorithm

The deletion algorithm follows these steps:

1. Search for the node to be deleted.
2. If the node is not found, the deletion is complete (nothing to delete).
3. If the node is found, handle one of the three cases:
   • Case 1: Leaf Node - Simply remove the node by setting its parent's reference to null.
   • Case 2: Node with One Child - Replace the node with its child.
   • Case 3: Node with Two Children - Find the node's in-order successor (the smallest value in its right subtree), replace the node's value with the successor's value, and then delete the successor.

Implementation

Here's how we implement the delete operation in TypeScript:

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;
 
  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
 
class BinarySearchTree {
  root: TreeNode | null;
 
  constructor() {
    this.root = null;
  }
 
  delete(value: number): void {
    this.root = this.deleteNode(this.root, value);
  }
 
  private deleteNode(root: TreeNode | null, value: number): TreeNode | null {
    // Base case: if the tree is empty
    if (root === null) {
      return null;
    }
 
    // Recursively search for the node to delete
    if (value < root.value) {
      root.left = this.deleteNode(root.left, value);
    } else if (value > root.value) {
      root.right = this.deleteNode(root.right, value);
    } else {
      // Node found, now delete it
 
      // Case 1: Leaf node (no children)
      if (root.left === null && root.right === null) {
        return null;
      }
 
      // Case 2: Node with only one child
      if (root.left === null) {
        return root.right;
      }
      if (root.right === null) {
        return root.left;
      }
 
      // Case 3: Node with two children
      // Find the inorder successor (smallest node in right subtree)
      root.value = this.findMinValue(root.right);
 
      // Delete the inorder successor
      root.right = this.deleteNode(root.right, root.value);
    }
 
    return root;
  }
 
  private findMinValue(node: TreeNode): number {
    let minValue = node.value;
    while (node.left !== null) {
      minValue = node.left.value;
      node = node.left;
    }
    return minValue;
  }
}

Example

Let's consider the following binary search tree:

        10
       /  \
      5    15
     / \  / \
    3   7 12 18

Let's delete the node with value 5:

1. Find the node with value 5.
2. This node has two children (3 and 7), so we need to find its in-order successor.
3. The in-order successor is the smallest value in the right subtree of 5, which is 7.
4. Replace the value of the node with 7.
5. Delete the node with value 7 from the right subtree of the original node.

The resulting tree would look like:

        10
       /  \
      7    15
     /    / \
    3    12 18

Time and Space Complexity

Time Complexity: O(h) where h is the height of the tree. In a balanced BST, this is O(log n), but in the worst case (a skewed tree), it can be O(n).

Space Complexity: O(h) for the recursive call stack, where h is the height of the tree.