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.

Practice

1. What happens when you delete a leaf node (a node with no children) in a Binary Search Tree (BST)?

easy

A. The entire tree is rebuilt

B. The node is replaced by its right child

C. The node is replaced by its left child

D. The node is simply removed without affecting other nodes

Solution

1. Step 1: Understand leaf node deletion

   A leaf node has no children, so deleting it means just removing it from the tree.

2. Step 2: Effect on the BST

   Since it has no children, no other nodes need to be moved or replaced.

3. Final Answer:

   The node is simply removed without affecting other nodes -> Option D

4. Quick Check:

   Leaf node deletion = simple removal [OK]

Hint: Leaf nodes delete by direct removal only [OK]

Common Mistakes:

• Thinking children need rearrangement
• Replacing leaf with child nodes
• Rebuilding the whole tree

2. Which of the following is the correct TypeScript function signature for deleting a node from a BST?

easy

A. function deleteNode(key: number): TreeNode

B. function deleteNode(root: number, key: TreeNode): void

C. function deleteNode(root: TreeNode | null, key: number): TreeNode | null

D. function deleteNode(root: TreeNode, key: string): TreeNode

Solution

1. Step 1: Analyze parameter types

   The root should be a TreeNode or null, and key should be a number to identify the node.

2. Step 2: Analyze return type

   The function returns the updated root node or null if tree becomes empty.

3. Final Answer:

   function deleteNode(root: TreeNode | null, key: number): TreeNode | null -> Option C

4. Quick Check:

   Correct parameter and return types = function deleteNode(root: TreeNode | null, key: number): TreeNode | null [OK]

Hint: Root can be null; key is number; returns updated root [OK]

Common Mistakes:

• Swapping parameter types
• Using wrong return type
• Using string instead of number for key

3. Given the BST below and the delete operation deleteNode(root, 10), what is the in-order traversal of the BST after deletion?

BST structure:
15
/ \
10 20
/ \ \
8 12 25

medium

A. [8, 12, 15, 20, 25]

B. [8, 10, 12, 15, 20, 25]

C. [8, 15, 20, 25]

D. [12, 15, 20, 25]

Solution

1. Step 1: Delete node 10 with two children

   Node 10 has two children (8 and 12). Replace it with its inorder successor, which is 12.

2. Step 2: Remove node 12 from its original position

   After replacement, remove node 12 from right subtree of 10.

3. Step 3: In-order traversal after deletion

   Traversal is [8, 12, 15, 20, 25].

4. Final Answer:

   [8, 12, 15, 20, 25] -> Option A

5. Quick Check:

   Inorder after deleting 10 = [8, 12, 15, 20, 25] [OK]

Hint: Replace node with inorder successor for two children [OK]

Common Mistakes:

• Not replacing node 10 correctly
• Leaving node 10 in tree
• Incorrect traversal order

4. Consider this TypeScript code snippet for deleting a node from a BST. What is the bug?

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if (!root) return null;
  if (key < root.val) {
    root.left = deleteNode(root.left, key);
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key);
  } else {
    if (!root.left) return root.right;
    if (!root.right) return root.left;
    let minNode = findMin(root.right);
    root.val = minNode.val;
    deleteNode(root.right, minNode.val);
  }
  return root;
}

medium

A. No return statement after deletion

B. Missing assignment of root.right after deleting minNode

C. Wrong comparison operators for key

D. Incorrect base case for empty root

Solution

1. Step 1: Analyze deletion of minNode

   After copying minNode's value, the code calls deleteNode on root.right but does not assign the result back to root.right.

2. Step 2: Effect of missing assignment

   Without assignment, the minNode is not removed from the right subtree, causing duplicate values.

3. Final Answer:

   Missing assignment of root.right after deleting minNode -> Option B

4. Quick Check:

   Assign updated subtree after deletion [OK]

Hint: Always assign recursive delete result back to subtree [OK]

Common Mistakes:

• Forgetting to assign after recursive delete
• Misplacing base case
• Using wrong comparison signs

5. You have a BST with nodes: 30, 20, 40, 10, 25, 35, 50. You delete node 30 (root). Which node becomes the new root after deletion using the standard BST delete operation?

hard

A. 35

B. 25

C. 40

D. 20

Solution

1. Step 1: Identify node 30's children

   Node 30 has two children: left subtree with 20 and right subtree with 40.

2. Step 2: Find inorder successor of 30

   Inorder successor is the smallest node in right subtree, which is 35.

3. Step 3: Replace 30 with 35 and delete 35 from right subtree

   35 replaces 30 as root, and 35 is removed from its original position.

4. Final Answer:

   35 -> Option A

5. Quick Check:

   Inorder successor replaces deleted node [OK]

Hint: Use inorder successor (smallest right subtree) for two-child node deletion [OK]

Common Mistakes:

• Using inorder predecessor instead
• Choosing wrong replacement node
• Not updating root after deletion