Binary Search Tree - Insert, Delete

binarySearchTree.js

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

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

    insert(value) {
        const newNode = new TreeNode(value);

        if (this.root === null) {
            this.root = newNode;
            return;
        }

        let currentNode = this.root;

        while (true) {
            if (value < currentNode.value) {
                // Go left
                if (!currentNode.left) {
                    currentNode.left = newNode;
                    return;
                }
                currentNode = currentNode.left;
            } else {
                // Go right
                if (!currentNode.right) {
                    currentNode.right = newNode;
                    return;
                }
                currentNode = currentNode.right;
            }
        }
    }

    delete(value) {
        this.root = this._deleteNode(this.root, value);
    }

    _deleteNode(node, value) {
        if (node === null) {
            return node;
        }

        if (value < node.value) {
            node.left = this._deleteNode(node.left, value);
        } else if (value > node.value) {
            node.right = this._deleteNode(node.right, value);
        } else {
            // Node to be deleted found

            // Case 1: Node has no children (leaf node)
            if (!node.left && !node.right) {
                return null;
            }

            // Case 2: Node has one child
            if (!node.left) {
                return node.right;
            }
            if (!node.right) {
                return node.left;
            }

            // Case 3: Node has two children
            // Replace with the smallest value in the right subtree (in-order successor)
            const minValue = this._findMin(node.right);
            node.value = minValue;
            node.right = this._deleteNode(node.right, minValue);
        }

        return node;
    }

    _findMin(node) {
        while (node.left !== null) {
            node = node.left;
        }
      
        return node.value;
    }
}

const bst = new BinarySearchTree();

bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(2);
bst.insert(7);
bst.insert(12);
bst.insert(17);

console.log("Tree before deletion:");
console.log(bst.root);

bst.delete(10);

console.log("Tree after deleting 10:");
console.log(bst.root);