BST Delete Operation in DSA Javascript - 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 BST properties intact.

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

📋 What You'll Learn

Create a BST by inserting these exact numbers in order: 50, 30, 70, 20, 40, 60, 80

Create a variable called target and set it to 50

Implement a function called deleteNode that deletes target from the BST

Print the BST nodes in ascending order after deletion using an inorder traversal

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to keep data sorted and allow fast insertions, deletions, and lookups.

💼 Career

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

1

Create the BST with given numbers

Create a class called Node with val, left, and right properties. Then create a class called BST with an empty root. Add an insert method to insert numbers. Insert these numbers in order: 50, 30, 70, 20, 40, 60, 80 into the BST instance called tree.

DSA Javascript

// Define Node and BST classes
// Insert the numbers 50, 30, 70, 20, 40, 60, 80 into tree
// Your code here

Hint

Define Node and BST classes first. Use a loop inside insert to find the correct place for each number.

2

Set the target number to delete

Create a variable called target and set it to 50.

DSA Javascript

class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor() {
        this.root = null;
    }

    insert(val) {
        const newNode = new Node(val);
        if (!this.root) {
            this.root = newNode;
            return;
        }
        let current = this.root;
        while (true) {
            if (val < current.val) {
                if (!current.left) {
                    current.left = newNode;
                    return;
                }
                current = current.left;
            } else {
                if (!current.right) {
                    current.right = newNode;
                    return;
                }
                current = current.right;
            }
        }
    }
}

const tree = new BST();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);

// Create a variable called target and set it to 50
// Your code here

Hint

Just create a constant named target and assign it the value 50.

3

Implement the deleteNode function

Add a method called deleteNode inside the BST class that takes root and key as parameters. It should delete the node with value key from the BST and return the new root. Use this method to delete target from tree.root and update tree.root.

DSA Javascript

class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor() {
        this.root = null;
    }

    insert(val) {
        const newNode = new Node(val);
        if (!this.root) {
            this.root = newNode;
            return;
        }
        let current = this.root;
        while (true) {
            if (val < current.val) {
                if (!current.left) {
                    current.left = newNode;
                    return;
                }
                current = current.left;
            } else {
                if (!current.right) {
                    current.right = newNode;
                    return;
                }
                current = current.right;
            }
        }
    }

    // Add deleteNode method here
    // Your code here
}

const tree = new BST();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);

const target = 50;

// Delete target from tree.root and update tree.root
// Your code here

Hint

Use recursion to find the node to delete. Handle three cases: no child, one child, two children. For two children, replace with smallest node in right subtree.

4

Print the BST in sorted order after deletion

Add a function called inorder that takes a node and returns an array of values in ascending order by traversing the BST in order. Use this function to print the sorted values of tree.root after deletion.

DSA Javascript

class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor() {
        this.root = null;
    }

    insert(val) {
        const newNode = new Node(val);
        if (!this.root) {
            this.root = newNode;
            return;
        }
        let current = this.root;
        while (true) {
            if (val  root.val) {
            root.right = this.deleteNode(root.right, key);
        } else {
            if (!root.left) return root.right;
            if (!root.right) return root.left;
            let minLargerNode = root.right;
            while (minLargerNode.left) {
                minLargerNode = minLargerNode.left;
            }
            root.val = minLargerNode.val;
            root.right = this.deleteNode(root.right, minLargerNode.val);
        }
        return root;
    }
}

const tree = new BST();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);

const target = 50;
tree.root = tree.deleteNode(tree.root, target);

// Add inorder function and print sorted values
// Your code here

Hint

Use recursion to visit left child, then current node, then right child. Collect values in an array and print them joined by ' -> ' ending with ' -> null'.

Practice

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

easy

A. The node is simply removed without affecting other nodes.

B. The entire tree is rebuilt from scratch.

C. The node's children replace it in the tree.

D. The root node is always changed.

Solution

1. Step 1: Understand leaf node deletion

   A leaf node has no children, so removing it does not affect other nodes.

2. Step 2: Effect on BST structure

   Since no children exist, simply remove the node and update its parent's pointer to null.

3. Final Answer:

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

4. Quick Check:

   Leaf node deletion = simple removal [OK]

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

Common Mistakes:

• Thinking children replace the node when none exist
• Assuming root always changes
• Believing tree rebuild is needed

2. Which of the following is the correct syntax to delete a node with value key from a BST in JavaScript?

easy

A. bst.deleteNode(key);

B. bst.delete(key);

C. bst.remove(key);

D. bst.erase(key);

Solution

1. Step 1: Identify common BST delete method

   In many JavaScript BST implementations, the method to delete a node is named delete.

2. Step 2: Check method naming conventions

   Methods like remove, erase, or deleteNode are not standard or common in JavaScript BST examples.

3. Final Answer:

   bst.delete(key); -> Option B

4. Quick Check:

   Standard BST delete method = delete() [OK]

Hint: Use bst.delete(key) to remove nodes [OK]

Common Mistakes:

• Using remove() or erase() which are not standard
• Confusing delete keyword with method name
• Using deleteNode() which is uncommon

3. Consider this BST and the delete operation:

    10
   /  \
  5    15
       / \
      12  20

What will be the in-order traversal output after deleting node with value 15?

medium

A. [5, 10, 12, 15, 20]

B. [5, 10, 20]

C. [5, 10, 12, 20]

D. [5, 10, 15, 20]

Solution

1. Step 1: Identify node to delete and its children

   Node 15 has two children: 12 (left) and 20 (right).

2. Step 2: Replace node 15 with its in-order successor

   The in-order successor is the smallest node in right subtree, which is 20. Replace 15 with 20 and delete original 20 node.

3. Step 3: Perform in-order traversal

   In-order traversal visits nodes in ascending order: 5, 10, 12, 20.

4. Final Answer:

   [5, 10, 12, 20] -> Option C

5. Quick Check:

   In-order after deleting 15 = [5, 10, 12, 20] [OK]

Hint: Replace deleted node with in-order successor [OK]

Common Mistakes:

• Removing 15 without replacement
• Using in-order predecessor instead of successor
• Forgetting to delete the successor node

4. The following code attempts to delete a node from a BST but causes an error. What is the main issue?

function deleteNode(root, key) {
  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;
    else if (!root.right) return root.left;
    let minNode = findMin(root.right);
    root.val = minNode.val;
    // Missing deletion of minNode here
  }
  return root;
}

function findMin(node) {
  while (node.left) node = node.left;
  return node;
}

medium

A. The function does not handle leaf nodes correctly.

B. The base case for recursion is missing.

C. The function uses incorrect comparison operators.

D. The code does not delete the in-order successor node after copying its value.

Solution

1. Step 1: Analyze deletion of node with two children

   When deleting a node with two children, we replace its value with the in-order successor's value.

2. Step 2: Check if in-order successor node is deleted

   The code copies the successor's value but does not delete the successor node itself, causing duplicate values and incorrect tree.

3. Final Answer:

   The code does not delete the in-order successor node after copying its value. -> Option D

4. Quick Check:

   Must delete successor node after value copy [OK]

Hint: Always delete successor node after copying value [OK]

Common Mistakes:

• Forgetting to delete the in-order successor node
• Missing base case (though present here)
• Incorrectly handling leaf nodes
• Using wrong comparison operators

5. You have a BST with nodes: 8, 3, 10, 1, 6, 14, 4, 7, 13.
After deleting node 3, what is the correct in-order traversal of the BST?

hard

A. [1, 4, 6, 7, 8, 10, 13, 14]

B. [1, 3, 4, 6, 7, 8, 10, 13, 14]

C. [1, 6, 7, 8, 10, 13, 14]

D. [1, 4, 7, 8, 10, 13, 14]

Solution

1. Step 1: Identify node 3 and its children

   Node 3 has two children: 1 (left) and 6 (right). 6 has children 4 and 7.

2. Step 2: Delete node 3 by replacing with in-order successor

   The in-order successor of 3 is 4 (smallest in right subtree). Replace 3 with 4, then delete original 4 node.

3. Step 3: Perform in-order traversal after deletion

   In-order traversal visits nodes in ascending order: 1, 4, 6, 7, 8, 10, 13, 14.

4. Final Answer:

   [1, 4, 6, 7, 8, 10, 13, 14] -> Option A

5. Quick Check:

   In-order after deleting 3 = [1, 4, 6, 7, 8, 10, 13, 14] [OK]

Hint: Replace deleted node with in-order successor, then traverse [OK]

Common Mistakes:

• Forgetting to delete the in-order successor node
• Using in-order predecessor instead
• Skipping nodes in traversal