Building and Understanding Binary Search Trees in JavaScript

Binary Search Trees (BSTs) are one of the most fundamental and widely used data structures in computer science. They allow for efficient searching, insertion, and deletion of data. In this blog, we’ll break down the concepts of BSTs and walk you through implementing one in JavaScript with a complete example.

---

What is a Binary Search Tree (BST)?

A Binary Search Tree is a type of binary tree where each node has at most two children, and the nodes are arranged in a specific order:

1. Left Subtree: Contains nodes with values less than the parent node.

2. Right Subtree: Contains nodes with values greater than the parent node.

This property makes BSTs efficient for searching, as you can eliminate half of the tree at each step, achieving a time complexity of O(log n) for search operations in a balanced tree.

---

Key Operations of a Binary Search Tree

1. Insertion: Adding a new value to the tree.

2. Search: Finding if a value exists in the tree.

3. Deletion: Removing a value while maintaining the tree structure.

4. Traversal: Visiting all nodes in a specific order (e.g., inorder, preorder, or postorder).

---

Implementing a Binary Search Tree in JavaScript

Here’s a step-by-step guide to implementing a BST in JavaScript:

1. Define the Node Class

Each node in the tree will have a value (data) and pointers to its left and right children.

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

2. Define the Binary Search Tree Class

The BST class will manage the root node and provide methods for various operations.

Insertion

We’ll create a helper method to find the correct position in the tree to insert a new node.

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

    insert(data) {
        const newNode = new Node(data);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    insertNode(node, newNode) {
        if (newNode.data < node.data) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }
}

Deletion

Deleting a node involves three cases:

1. No children: Simply remove the node.

2. One child: Replace the node with its child.

3. Two children: Replace the node with the minimum value from its right subtree.

remove(data) {
    this.root = this.removeNode(this.root, data);
}

removeNode(node, key) {
    if (node === null) return null;

    if (key < node.data) {
        node.left = this.removeNode(node.left, key);
        return node;
    } else if (key > node.data) {
        node.right = this.removeNode(node.right, key);
        return node;
    } else {
        if (node.left === null && node.right === null) {
            node = null;
            return node;
        }

        if (node.left === null) return node.right;
        else if (node.right === null) return node.left;

        const aux = this.findMinNode(node.right);
        node.data = aux.data;
        node.right = this.removeNode(node.right, aux.data);
        return node;
    }
}

findMinNode(node) {
    if (node.left === null) return node;
    else return this.findMinNode(node.left);
}

Traversals

• Inorder: Left -> Root -> Right (sorted order for BST).

• Preorder: Root -> Left -> Right.

• Postorder: Left -> Right -> Root.

inorder(node) {
    if (node !== null) {
        this.inorder(node.left);
        console.log(node.data);
        this.inorder(node.right);
    }
}

preorder(node) {
    if (node !== null) {
        console.log(node.data);
        this.preorder(node.left);
        this.preorder(node.right);
    }
}

postorder(node) {
    if (node !== null) {
        this.postorder(node.left);
        this.postorder(node.right);
        console.log(node.data);
    }
}

---

Example: Using the Binary Search Tree

Here’s how you can use the above implementation:

const BST = new BinarySearchTree();

// Insert nodes
BST.insert(15);
BST.insert(25);
BST.insert(10);
BST.insert(7);
BST.insert(22);
BST.insert(17);
BST.insert(13);
BST.insert(5);
BST.insert(9);
BST.insert(27);

// Perform traversals
console.log("Inorder Traversal:");
BST.inorder(BST.root);

console.log("Preorder Traversal:");
BST.preorder(BST.root);

console.log("Postorder Traversal:");
BST.postorder(BST.root);

// Remove nodes
BST.remove(7);
console.log("After removing 7 (Inorder Traversal):");
BST.inorder(BST.root);

---

Visualizing the Tree

For the example above, the tree will look like this:

        15
      /    \
    10      25
   / \     /  \
  7  13   22  27
 / \
5   9

After removing 7:

        15
      /    \
    10      25
   / \     /  \
  9  13   22  27
 /
5

---

Wrap-Up

Binary Search Trees are a cornerstone of efficient algorithms and data structures. They provide a solid foundation for searching, sorting, and managing hierarchical data. Understanding BSTs and their operations will not only make you a better programmer but also help you tackle real-world problems effectively.

Happy coding! 🚀