BST Delete Operation in DSA Typescript - Build from Scratch

BST Delete Operation

📖 Scenario: You are managing a collection of unique numbers using a Binary Search Tree (BST). Sometimes, you need to remove a number from this collection while keeping the tree organized.

🎯 Goal: Build a TypeScript program that creates a BST, sets a value to delete, performs the delete operation correctly, and prints the tree in order after deletion.

📋 What You'll Learn

Create a BST with the exact nodes: 50, 30, 70, 20, 40, 60, 80

Create a variable called keyToDelete with the value 50

Implement a deleteNode function to remove the node with keyToDelete from the BST

Print the BST nodes in ascending order after deletion using inOrderTraversal

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to keep data sorted and allow fast search, insert, and delete operations.

💼 Career

Understanding BST delete operation is important for software engineers working on data storage, search engines, and performance-critical applications.

1

Create the BST nodes

Create a class called TreeNode with val, left, and right properties. Then create the BST with nodes having these exact values: 50, 30, 70, 20, 40, 60, 80, linked correctly to form a BST.

DSA Typescript

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

// Your code here to create the BST nodes and link them

Hint

Define the TreeNode class first. Then create nodes and link them to form the BST exactly as described.

2

Set the key to delete

Create a variable called keyToDelete and set it to 50.

DSA Typescript

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

const root = new TreeNode(50);
root.left = new TreeNode(30);
root.right = new TreeNode(70);
root.left.left = new TreeNode(20);
root.left.right = new TreeNode(40);
root.right.left = new TreeNode(60);
root.right.right = new TreeNode(80);

// Your code here to set keyToDelete

Hint

Just create a constant named keyToDelete and assign it the number 50.

3

Implement the deleteNode function

Write a function called deleteNode that takes root: TreeNode | null and key: number as parameters. It should return the root of the BST after deleting the node with value key. Use the standard BST delete logic: if the node has two children, replace it with its inorder successor.

DSA Typescript

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

const root = new TreeNode(50);
root.left = new TreeNode(30);
root.right = new TreeNode(70);
root.left.left = new TreeNode(20);
root.left.right = new TreeNode(40);
root.right.left = new TreeNode(60);
root.right.right = new TreeNode(80);

const keyToDelete = 50;

// Your code here to implement deleteNode function

Hint

Use recursion to find the node. Handle three cases: no child, one child, two children. For two children, find the smallest node in the right subtree (inorder successor) and replace.

4

Print the BST after deletion

Write a function called inOrderTraversal that takes root: TreeNode | null and prints the node values in ascending order separated by spaces. Then call deleteNode with root and keyToDelete, and print the BST nodes after deletion using inOrderTraversal.

DSA Typescript

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

const root = new TreeNode(50);
root.left = new TreeNode(30);
root.right = new TreeNode(70);
root.left.left = new TreeNode(20);
root.left.right = new TreeNode(40);
root.right.left = new TreeNode(60);
root.right.right = new TreeNode(80);

const keyToDelete = 50;

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

// Your code here to implement inOrderTraversal and print the BST after deletion

Hint

Use recursion to print left subtree, current node, then right subtree. Call deleteNode first, then print the tree.

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