Binary Search Trees (BSTs) Algorithm

Binary Search Trees (BSTs) are fundamental data structures that enable efficient storage and retrieval of data in sorted order

Binary Search Trees (BSTs) are hierarchical data structures consisting of nodes, where each node has at most two children: a left child and a right child. BSTs follow the property that the value of each node's left child is less than the node's value, and the value of each node's right child is greater than the node's value.

BSTs support efficient insertion, deletion, and search operations, making them suitable for applications requiring fast retrieval and sorted storage of data. Traversal techniques such as inorder, preorder, and postorder traversals enable systematic access to the elements of a BST.

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) {
            this.root = newNode;
            return this;
        }

        let current = this.root;

        while (true) {
            if (value === current.value) return undefined;
            if (value < current.value) {
                if (!current.left) {
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if (!current.right) {
                    current.right = newNode;
                    return this;
                }
                current = current.right;
            }
        }
    }

    search(value) {
        let current = this.root;
        while (current) {
            if (value === current.value) return true;
            if (value < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }
}

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

console.log("Search for 7:", bst.search(7)); // Output: true
console.log("Search for 20:", bst.search(20)); // Output: false

The time complexity of insertion, search, and deletion operations in BSTs is O(h), where h is the height of the tree. In a balanced BST, the height is approximately log(n), where n is the number of nodes, resulting in efficient operations.

BSTs find applications in various domains, including database indexing, symbol tables in compilers, and organizing data in file systems, where fast retrieval and sorted storage are crucial.