🔍 From Data to Decisions: Understanding Binary Search Trees in JavaScript

In the last two posts, we covered what binary trees are and how to traverse them. Now it’s time to take a step further and explore a powerful, efficient variation: the Binary Search Tree (BST).

A Binary Search Tree enables fast insertion, lookup, and deletion of elements. It’s one of the most important data structures you'll come across—especially in interviews and system design discussions.

Let’s break it all down in this post:

• What makes a tree a BST
• How to implement one in JavaScript
• How to insert, search, and delete values
• Why balancing matters
• Time complexity and real-world use cases

---

🌲 What is a Binary Search Tree?

A Binary Search Tree (BST) is a binary tree with an extra property:

For every node:

• All values in the left subtree are less than the node's value
• All values in the right subtree are greater than the node's value

This structure allows binary search-like efficiency, enabling fast lookups in O(log n) time (if the tree is balanced).

🧠 Visual Example:

       10
      /  \
     5    15
    / \     \
   3   7     20

• 5 < 10 → on the left
• 15 > 10 → on the right
• 3 < 5, 7 > 5, 20 > 15 → BST rules preserved

---

🛠 Implementing a Binary Search Tree in JavaScript

Step 1: Node class (same as before)

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

Step 2: BST class with Insert

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

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

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

    let current = this.root;
    while (true) {
      if (value === current.value) return; // avoid duplicates

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

👇 Example Usage:

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);

---

🔍 Searching in a BST

contains(value) {
  let current = this.root;

  while (current) {
    if (value === current.value) return true;
    current = value < current.value ? current.left : current.right;
  }

  return false;
}

Time complexity:

• Best/Average case: O(log n)
• Worst case (skewed tree): O(n)

---

❌ Deleting a Node in a BST

Deletion is the most complex part. There are 3 possible cases:

📦 Case 1: Node has no children

Just remove the node.

📦 Case 2: Node has one child

Replace the node with its child.

📦 Case 3: Node has two children

• Find the in-order successor (smallest value in right subtree)
• Replace node’s value with it
• Recursively delete the successor

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

_deleteNode(node, value) {
  if (!node) return null;

  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 found
    if (!node.left && !node.right) return null;
    if (!node.left) return node.right;
    if (!node.right) return node.left;

    // Two children
    let minRight = node.right;
    while (minRight.left) {
      minRight = minRight.left;
    }

    node.value = minRight.value;
    node.right = this._deleteNode(node.right, minRight.value);
  }

  return node;
}

---

⚖️ Time Complexity of BST Operations

Operation	Best / Average	Worst Case (unbalanced)
Insert	O(log n)	O(n)
Search	O(log n)	O(n)
Delete	O(log n)	O(n)

💡 Note: When a BST becomes unbalanced (like a linked list), it loses its efficiency. This is why self-balancing trees like AVL Trees and Red-Black Trees exist.

---

🧠 Real-World Use Cases of BSTs

• Implementing efficient sets or maps
• Searching sorted hierarchical data
• Syntax trees in compilers
• Tree-based range queries and auto-complete systems

---

🧹 BST vs Binary Tree (Quick Recap)

Feature	Binary Tree	Binary Search Tree (BST)
Node arrangement	No rules	Left < Root < Right
Lookup speed	O(n)	O(log n) (if balanced)
Use cases	Hierarchies, layouts	Searching, ordered data

---

✅ Summary

In this post, we:

• Learned what makes a Binary Search Tree special
• Built a BST class in JavaScript
• Implemented insert, search, and delete
• Reviewed time complexity and real-world applications

Now you have a full grasp of how BSTs work and how to implement one from scratch.