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.