Binary Search Trees

The BST Property

A Binary Search Tree is a binary tree with one critical invariant: for every node N, all values in its left subtree are strictly less than N, and all values in its right subtree are strictly greater than N. This ordering property enables efficient search, insertion, and deletion — all O(log n) in a balanced tree.

The key word is balanced. An unbalanced BST (one where most nodes have only right or only left children) degrades to O(n) operations — essentially a linked list. Self-balancing variants like AVL trees and Red-Black trees automatically maintain balance after every insert or delete.

BST Implementation

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

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

  // Insert: O(log n) average, O(n) worst
  insert(value) {
    const newNode = new BSTNode(value);
    if (!this.root) { this.root = newNode; return; }

    let current = this.root;
    while (true) {
      if (value === current.value) return; // no 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;
      }
    }
  }

  // Search: O(log n) average
  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }

  // Minimum value: always the leftmost node
  findMin() {
    let current = this.root;
    while (current && current.left) current = current.left;
    return current ? current.value : null;
  }

  // Maximum value: always the rightmost node
  findMax() {
    let current = this.root;
    while (current && current.right) current = current.right;
    return current ? current.value : null;
  }

  // Inorder traversal yields sorted output
  inorder(node = this.root, result = []) {
    if (!node) return result;
    this.inorder(node.left, result);
    result.push(node.value);
    this.inorder(node.right, result);
    return result;
  }
}

const bst = new BST();
[5, 3, 7, 1, 4, 6, 8].forEach(v => bst.insert(v));
console.log(bst.inorder()); // [1, 3, 4, 5, 6, 7, 8] — sorted!
console.log(bst.search(4)); // true
console.log(bst.findMin()); // 1

BST Deletion

Deletion is the trickiest BST operation because you must handle three cases:

• 1. Leaf node — just remove it.
• 2. One child — replace the node with its child.
• 3. Two children — replace the node's value with its in-order successor (smallest node in the right subtree), then delete the successor.

function deleteNode(root, value) {
  if (!root) return null;

  if (value < root.value) {
    root.left = deleteNode(root.left, value);
  } else if (value > root.value) {
    root.right = deleteNode(root.right, value);
  } else {
    // Case 1 & 2: 0 or 1 child
    if (!root.left) return root.right;
    if (!root.right) return root.left;

    // Case 3: 2 children — find in-order successor
    let successor = root.right;
    while (successor.left) successor = successor.left;
    root.value = successor.value;
    root.right = deleteNode(root.right, successor.value);
  }
  return root;
}