BST Delete Operation in DSA Typescript

Mental Model

Deleting a node from a BST means removing it while keeping the tree sorted. We adjust links so the tree stays balanced and ordered.

Analogy: Imagine removing a book from a sorted bookshelf. If the book is alone, just take it out. If it has neighbors, shift or replace it so the order stays perfect.

      5
     / \
    3   7
   / \   \
  2   4   8

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, delete node with value 3

Goal: Remove node 3 and keep BST properties intact

Step 1: Find node 3 to delete

      5
     / \
    [3] 7
   / \   \
  2   4   8

Why: We must locate the node to remove it

Step 2: Node 3 has two children, find its inorder successor (smallest in right subtree), which is 4

      5
     / \
    3   7
   / \   \
  2  [4]  8

Why: Replacing node 3 with 4 keeps BST order

Step 3: Replace node 3's value with 4

      5
     / \
    4   7
   / \   \
  2   4   8

Why: We copy successor's value to node 3

Step 4: Delete original node 4 (successor), which has no left child, replace it with its right child (null)

      5
     / \
    4   7
   /     \
  2       8

Why: Remove duplicate successor node, maintaining BST

Result:

      5
     / \
    4   7
   /     \
  2       8

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if (root === null) return null; // base case: empty tree

  if (key < root.val) {
    root.left = deleteNode(root.left, key); // search left subtree
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key); // search right subtree
  } else {
    // found node to delete
    if (root.left === null) {
      return root.right; // replace node with right child
    } else if (root.right === null) {
      return root.left; // replace node with left child
    } else {
      // node with two children: find inorder successor
      let successor = root.right;
      while (successor.left !== null) {
        successor = successor.left; // find smallest in right subtree
      }
      root.val = successor.val; // copy successor value
      root.right = deleteNode(root.right, successor.val); // delete successor
    }
  }
  return root;
}

function printBST(root: TreeNode | null): string {
  if (root === null) return "null";
  const leftStr = printBST(root.left);
  const rightStr = printBST(root.right);
  return `${root.val} -> (${leftStr}, ${rightStr})`;
}

// Driver code
const root = new TreeNode(5,
  new TreeNode(3,
    new TreeNode(2),
    new TreeNode(4)
  ),
  new TreeNode(7,
    null,
    new TreeNode(8)
  )
);

const newRoot = deleteNode(root, 3);
console.log(printBST(newRoot));

if (root === null) return null;

stop recursion if tree/subtree is empty

if (key < root.val) { root.left = deleteNode(root.left, key); }

search left subtree if key smaller

else if (key > root.val) { root.right = deleteNode(root.right, key); }

search right subtree if key larger

else { // found node to delete

handle deletion cases

if (root.left === null) { return root.right; }

replace node with right child if no left child

else if (root.right === null) { return root.left; }

replace node with left child if no right child

else { let successor = root.right; while (successor.left !== null) { successor = successor.left; } root.val = successor.val; root.right = deleteNode(root.right, successor.val); }

replace node with inorder successor and delete successor

return root;

return updated subtree root

Output

5 -> (4 -> (2 -> (null, null), null), 7 -> (null, 8 -> (null, null)))

Complexity Analysis

Time: O(h) where h is tree height because we traverse from root to leaf at most once

Space: O(h) due to recursion stack in worst case of skewed tree

vs Alternative: Compared to naive approach that rebuilds tree, this is efficient by only adjusting pointers locally

Edge Cases

Deleting from empty tree

Returns null immediately, no error

DSA Typescript

if (root === null) return null;

Deleting leaf node (no children)

Node is simply removed by returning null to parent

DSA Typescript

if (root.left === null) { return root.right; }

Deleting node with one child

Node replaced by its single child

DSA Typescript

else if (root.right === null) { return root.left; }

When to Use This Pattern

When you need to remove a value from a BST and keep it sorted, use the BST delete pattern that handles 0, 1, or 2 children cases carefully.

Common Mistakes

Mistake: Not handling the two children case by replacing with inorder successor
Fix: Find the smallest node in right subtree, copy its value, then delete that successor node

Mistake: Forgetting to update parent's child pointer after deletion
Fix: Always assign the recursive deleteNode result back to root.left or root.right

Summary

Deletes a node from a BST while keeping the tree sorted.

Use when you need to remove a value from a BST without breaking its order.

The key is replacing a node with two children by its inorder successor to maintain BST properties.