Speed:

Binary Search Tree (BST)

Search: O(log n)Insert: O(log n)Delete: O(log n)

🌳BST Operations

A BST starts empty. Each node has at most two children: left (smaller values) and right (larger values).

Insert by comparing with current node. Go left if smaller, right if larger. Create new node when reaching null.

Start at root. Compare target with current node. Go left if smaller, right if larger, until found or null.

Three cases: no children (remove), one child (replace with child), two children (replace with successor).

🔧Setup - Node Structure

The foundation of a Binary Search Tree lies in its node structure. Each node contains a data value and two pointers: one to the left child (for smaller values) and one to the right child (for larger values). The BST class maintains a reference to the root node, which serves as the entry point to the entire tree. Initially, the tree is empty with a null root. This simple but powerful structure enables the BST to maintain sorted order automatically as elements are added or removed.

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

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

➕Add - Insert Operation

Insertion in a BST follows a recursive approach that maintains the tree's ordering property. Starting from the root, we compare the new value with the current node's value. If the new value is smaller, we move to the left subtree; if larger, we move to the right subtree. This continues until we reach a null position where the new node can be inserted. The process ensures that all values to the left of any node are smaller, and all values to the right are larger, preserving the BST property. In a balanced tree, insertion takes O(log n) time.

insert(data) {
    this.root = this.insertNode(this.root, data);
}

insertNode(node, data) {
    if (node === null) {
        return new Node(data);
    }
    
    if (data < node.data) {
        node.left = this.insertNode(node.left, data);
    } else if (data > node.data) {
        node.right = this.insertNode(node.right, data);
    }
    
    return node;
}

🔍Search - Find Operation

Search operation in BST leverages the tree's ordering property to efficiently locate elements. Starting from the root, we compare the target value with the current node's value. If the target is smaller, we traverse to the left subtree; if larger, we go to the right subtree. This process continues until we either find the target value or reach a null node (indicating the value doesn't exist). In a balanced BST, this approach achieves O(log n) time complexity by eliminating half of the remaining nodes with each comparison.

search(data) {
    return this.searchNode(this.root, data);
}

searchNode(node, data) {
    if (node === null || node.data === data) {
        return node;
    }
    
    if (data < node.data) {
        return this.searchNode(node.left, data);
    }
    
    return this.searchNode(node.right, data);
}

🗑️Delete - Remove Operation

Deletion is the most complex BST operation due to three distinct cases that must be handled.Case 1: If the node has no children, simply remove it.Case 2: If the node has one child, replace the node with its child.Case 3: If the node has two children, find the inorder successor (smallest value in the right subtree), replace the node's value with the successor's value, then delete the successor. This maintains the BST property while ensuring the tree structure remains valid after deletion.

delete(data) {
    this.root = this.deleteNode(this.root, data);
}

deleteNode(node, data) {
    if (node === null) return null;
    
    if (data < node.data) {
        node.left = this.deleteNode(node.left, data);
    } else if (data > node.data) {
        node.right = this.deleteNode(node.right, data);
    } else {
        // No children
        if (!node.left && !node.right) return null;
        
        // One child
        if (!node.left) return node.right;
        if (!node.right) return node.left;
        
        // Two children
        let successor = this.findMin(node.right);
        node.data = successor.data;
        node.right = this.deleteNode(node.right, successor.data);
    }
    return node;
}