← Index

Trees & Heaps

Binary Search Tree

A tree with an ordering rule — smaller left, bigger right.

What it is

A BST caps each node at two children and enforces an invariant: everything in the left subtree is smaller, everything in the right subtree is bigger. That invariant is what makes search, insert, and delete O(log n) on average — each comparison eliminates half the remaining tree, same idea as binary search on a sorted array. A degenerate/unbalanced BST (e.g. inserting already-sorted data) degrades to O(n), which is why self-balancing variants (AVL, Red-Black) exist.

Real-world examples

• Guessing a number between 1-100 with 'higher or lower' hints — each guess halves the remaining range, exactly like descending a BST.
• A well-organized dictionary you can flip open toward roughly where a word should be, instead of reading front to back.

Where you've probably used this already

• Database indexes (B-trees, a wider variant of this idea) are why a WHERE id = ? query doesn't scan the whole table.
• Autocomplete/range-query features backed by a sorted structure so 'give me everything between X and Y' stays fast.
• In-order traversal of a BST gives you sorted output for free — useful whenever a tree needs to be flattened back into order.

Complexity

Code

// Represents an individual node within the tree
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;   // Points to the left child (smaller values)
    this.right = null;  // Points to the right child (larger values)
  }
}

// Manages the tree structure and operations
class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // Insert a new value into the tree
  insert(value) {
    const newNode = new Node(value);
    
    if (this.root === null) {
      this.root = newNode;
      return this;
    }

    let current = this.root;
    while (true) {
      // Prevent duplicates (optional, depending on requirements)
      if (value === current.value) return undefined;

      // Go left if value is smaller
      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } 
      // Go right if value is larger
      else {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  // Look up a specific value in the tree
  find(value) {
    if (this.root === null) return false;

    let current = this.root;
    while (current) {
      if (value < current.value) {
        current = current.left; // Search left subtree
      } else if (value > current.value) {
        current = current.right; // Search right subtree
      } else {
        return current; // Value found
      }
    }
    return false; // Value not found
  }

  // In-order traversal (Left, Root, Right) - returns array sorted from smallest to largest
  inOrder(node = this.root, list = []) {
    if (node !== null) {
      this.inOrder(node.left, list);
      list.push(node.value);
      this.inOrder(node.right, list);
    }
    return list;
  }
}

// --- Example Usage ---

const bst = new BinarySearchTree();

// Populate the tree
bst.insert(10);
bst.insert(5);
bst.insert(13);
bst.insert(2);
bst.insert(7);

// Search for values
console.log("Find 7:", bst.find(7));   // Returns the Node object containing 7
console.log("Find 20:", bst.find(20)); // Returns false

// Get sorted array via in-order traversal
console.log("Sorted Tree values:", bst.inOrder()); 
// Output: [2, 5, 7, 10, 13]