Binary Search Tree (JS)

BST.js

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

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

    // Insert a value into the BST
    insert(value) {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            return this;
        }

        let current = this.root;
        while (true) {
            if (value < current.value) {
                if (current.left === null) {
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else if (value > current.value) {
                if (current.right === null) {
                    current.right = newNode;
                    return this;
                }
                current = current.right;
            } else {
                return undefined; // Value already exists in the tree
            }
        }
    }

    // Search for a value in the BST
    search(value) {
        let current = this.root;
        while (current !== null) {
            if (value === current.value) {
                return true;
            }
            current = value < current.value ? current.left : current.right;
        }
        return false;
    }

    // Find the minimum value in a subtree
    findMin(node) {
        let current = node;
        while (current.left !== null) {
            current = current.left;
        }
        return current;
    }

    // Delete a node from the BST
    delete(value, node = this.root) {
        if (node === null) return null;

        if (value < node.value) {
            node.left = this.delete(value, node.left);
        } else if (value > node.value) {
            node.right = this.delete(value, node.right);
        } else {
            // Node with only one child or no child
            if (node.left === null) return node.right;
            if (node.right === null) return node.left;

            // Node with two children: Get the inorder successor (smallest in the right subtree)
            const temp = this.findMin(node.right);
            node.value = temp.value;

            // Delete the inorder successor
            node.right = this.delete(temp.value, node.right);
        }
        return node;
    }

    // In-order traversal (for debugging or display)
    inOrderTraversal(node = this.root, values = []) {
        if (node !== null) {
            this.inOrderTraversal(node.left, values);
            values.push(node.value);
            this.inOrderTraversal(node.right, values);
        }
        return values;
    }
}

// Example usage:
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);

console.log("In-order traversal:", bst.inOrderTraversal()); // [3, 5, 10, 15]
console.log("Search 15:", bst.search(15)); // true
console.log("Search 8:", bst.search(8));   // false

bst.delete(5);
console.log("In-order traversal:", bst.inOrderTraversal()); // [3, 10, 15]