BST Insert & Search

Insert and search nodes in a Binary Search Tree.

How it works

A Binary Search Tree (BST) maintains the invariant that for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This property enables O(log n) average-case insertion and search.

Insertion: Start at the root and compare the new value to each node. Go left if smaller, right if larger, until an empty slot is found.

Search: Follow the same comparison logic — the BST property guarantees you never need to explore both subtrees.

Worst-case degrades to O(n) for sorted input (a "stick" tree). Self-balancing variants like AVL trees and Red-Black trees avoid this.

Complexity

Best case

O(log n)

Average case

O(log n)

Worst case

O(n)

Space

O(h)

Visualizer

Generating steps…

Where it's used in the real world

Database engines

Index structures

BSTs underpin B-trees used in MySQL InnoDB and PostgreSQL for indexed column lookups. The ordering property ensures range queries scan only relevant subtrees.

Standard library maps

std::map / TreeMap

C++ std::map and Java TreeMap are implemented as red-black trees (balanced BSTs), providing O(log n) ordered key-value operations.

File systems

Directory trees

ext4 uses HTree (hash-tree, a BST variant) for large directory lookups, replacing linear scans with O(log n) filename resolution.

Implementation

class BSTNode {
  constructor(
    public value: number,
    public left: BSTNode | null = null,
    public right: BSTNode | null = null
  ) {}
}

class BST {
  root: BSTNode | null = null;

  insert(value: number): void {
    if (!this.root) { this.root = new BSTNode(value); return; }
    let cur = this.root;
    while (true) {
      if (value < cur.value) {
        if (!cur.left) { cur.left = new BSTNode(value); return; }
        cur = cur.left;
      } else {
        if (!cur.right) { cur.right = new BSTNode(value); return; }
        cur = cur.right;
      }
    }
  }

  search(value: number): BSTNode | null {
    let cur = this.root;
    while (cur) {
      if (cur.value === value) return cur;
      cur = value < cur.value ? cur.left : cur.right;
    }
    return null;
  }
}

const bst = new BST();
[5, 3, 7, 1, 4, 6, 8].forEach(v => bst.insert(v));
console.log(bst.search(4));  // BSTNode { value: 4, ... }
console.log(bst.search(9));  // null

Related algorithms

AVL Tree

Self-balancing BST that keeps height difference ≤ 1 via rotations.

O(log n)