Binary Search Trees

What Is a Binary Search Tree?

A BST is a binary tree with one killer rule: for any node, everything in its left subtree is smaller, and everything in its right subtree is bigger. That's it. That simple rule turns a regular tree into a searching machine.

Imagine searching for a word in a dictionary by always flipping to the middle. That's basically what a BST does. At every node, you decide: go left (smaller) or go right (bigger). Each step eliminates half the remaining data.

This is why BSTs give you O(log n) average lookup time. Not bad for a data structure that's also easy to implement and understand.

Insert, Search, Delete

Inserting follows the same logic as searching. Start at the root, compare, go left or right, and when you find an empty spot, put the new node there. It's like finding where a new book belongs on a sorted shelf.

Searching works the same way. Compare with the current node — if it matches, you found it. If it's smaller, go left. If it's bigger, go right. Keep going until you find it or hit a dead end.

Deletion is the trickiest part. If the node has no children, just remove it. If it has one child, replace it with that child. If it has two children, find the in-order successor (smallest value in the right subtree) and swap values.

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

function insert(root, value) {
  if (!root) return new BSTNode(value);
  if (value < root.value) {
    root.left = insert(root.left, value);
  } else if (value > root.value) {
    root.right = insert(root.right, value);
  }
  return root;
}

function search(root, value) {
  if (!root) return false;
  if (value === root.value) return true;
  if (value < root.value) return search(root.left, value);
  return search(root.right, value);
}

let root = null;
[5, 3, 7, 1, 4].forEach(v => root = insert(root, v));
console.log(search(root, 4));
console.log(search(root, 9));

Why BSTs Matter

BSTs combine the best of arrays and linked lists. Arrays give you fast access by index but slow inserts. Linked lists give you fast inserts but slow searches. BSTs give you fast search, insert, and delete — all O(log n) on average.

The catch is that a BST can become unbalanced. If you insert sorted data (1, 2, 3, 4, 5), you get a linked list instead of a balanced tree. That's where self-balancing trees like AVL trees come in, which we'll cover later.

For now, just remember: BSTs are your go-to when you need to maintain a sorted collection with fast lookups. They're simple, elegant, and get the job done.