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'.