Binary Search Tree

How a binary search tree works

A BST is a tree where each node has at most two children, with one rule that defines everything:

BST invariant: for every node, all keys in its left subtree are less than the node's key, and all keys in its right subtree are greater.

To search for a key, start at the root. If the key matches, done. If smaller, recurse on the left subtree. If larger, recurse on the right. Each step halves the remaining search space — when the tree is balanced, that's O(log n).

To insert a key, perform a search. Wherever the search ends (a missing left or right child), attach the new node there. The BST invariant is preserved.

To delete a key, find it. Three cases by how many children it has: zero (just remove), one (replace with child), two (replace with in-order successor). The two-child case is the only nontrivial one and is the source of most BST bugs.

Tree traversals

Four traversal orders cover every common need:

Order	Visit pattern	Yields	Used for
In-order	Left → Node → Right	Sorted (on BST)	Sorted iteration, range queries
Pre-order	Node → Left → Right	Root-first depth scan	Tree serialization, copy a tree
Post-order	Left → Right → Node	Children-first depth scan	Free a tree, evaluate expression tree
Level-order (BFS)	By depth, left to right	Breadth-first	Level-by-level processing, shortest path on tree

The first three are depth-first and use a stack (or recursion). Level-order is breadth-first and uses a queue.

Balance is everything

BST operations cost O(height). For a balanced tree of n nodes, height is O(log n) — about 20 for a million nodes. For a degenerate skewed tree (every node has only one child), height is O(n) — a million for a million nodes. The performance difference is roughly 50,000×.

How do you become unbalanced? By inserting keys in sorted or near-sorted order. Inserting [1, 2, 3, 4, 5] into a fresh BST produces a right-skewed chain. Production code never uses plain BSTs for this reason — it uses self-balancing variants:

	Plain BST	AVL tree	Red-black tree	B-tree
Search (worst)	O(n)	O(log n)	O(log n)	O(log n)
Balance	None	Strict (heights differ ≤ 1)	Looser (heights differ ≤ 2×)	Branching factor of dozens
Rotations on insert	None	Up to 1	Up to 2	Splits
Cache locality	Poor (pointer-heavy)	Poor	Poor	Excellent (large nodes)
Used in	Educational only	In-memory dictionaries	Java TreeMap, C++ std::map, Linux kernel	Databases, file systems

When to use a BST

• Ordered point + range queries. "Find key X" plus "find all keys between A and B" plus "find the smallest key > X." Hash tables can't do the latter two; BSTs can in O(log n + k) where k is the result size.
• Sorted iteration of a dynamic set. Insert, delete, and "give me everything in sorted order" all work with the same structure. Sorting once and storing in an array is faster for static data — BST shines when the data changes.
• In-memory ordered maps. Java's TreeMap, C++'s std::map, Rust's BTreeMap — all are ordered maps, all use balanced trees underneath.
• Auto-completion / nearest-key lookup. Find the largest key ≤ X (predecessor) or smallest key ≥ X (successor) — both are O(log n) on a BST, impossible on a hash table without sorting.

If you only need point queries on unchanging data, a sorted array with binary search is faster (better cache locality, no pointer overhead). If you need point queries on a dynamic set without ordering, a hash table is faster (O(1) average vs O(log n)).

JavaScript implementation

class TreeNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

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

  insert(key, value) {
    const newNode = new TreeNode(key, value);
    if (!this.root) { this.root = newNode; return; }
    let curr = this.root;
    while (true) {
      if (key < curr.key) {
        if (!curr.left) { curr.left = newNode; return; }
        curr = curr.left;
      } else if (key > curr.key) {
        if (!curr.right) { curr.right = newNode; return; }
        curr = curr.right;
      } else {
        curr.value = value;  // key exists — update
        return;
      }
    }
  }

  search(key) {
    let curr = this.root;
    while (curr) {
      if (key === curr.key) return curr.value;
      curr = key < curr.key ? curr.left : curr.right;
    }
    return undefined;
  }

  // In-order traversal: yields keys in sorted order
  *inorder(node = this.root) {
    if (!node) return;
    yield* this.inorder(node.left);
    yield [node.key, node.value];
    yield* this.inorder(node.right);
  }
}

Python implementation

class TreeNode:
    __slots__ = ('key', 'value', 'left', 'right')
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key, value):
        if self.root is None:
            self.root = TreeNode(key, value)
            return
        curr = self.root
        while True:
            if key < curr.key:
                if curr.left is None: curr.left = TreeNode(key, value); return
                curr = curr.left
            elif key > curr.key:
                if curr.right is None: curr.right = TreeNode(key, value); return
                curr = curr.right
            else:
                curr.value = value
                return

    def search(self, key):
        curr = self.root
        while curr:
            if key == curr.key: return curr.value
            curr = curr.left if key < curr.key else curr.right
        return None

    def inorder(self, node=None):
        if node is None: node = self.root
        if node is None: return
        yield from self.inorder(node.left) if node.left else iter([])
        yield (node.key, node.value)
        yield from self.inorder(node.right) if node.right else iter([])

Python's standard library doesn't ship a built-in BST. Use sortedcontainers.SortedDict (B-tree backed) for production ordered maps; it's faster than any pure-Python BST.

Famous BST problems

Invert a binary tree

Famous because Max Howell tweeted that Google rejected him for not solving it on a whiteboard. Three lines:

function invert(node) {
  if (!node) return null;
  [node.left, node.right] = [invert(node.right), invert(node.left)];
  return node;
}

Lowest Common Ancestor on a BST

The BST invariant makes LCA O(log n) — no full traversal needed:

function lca(root, p, q) {
  while (root) {
    if (p < root.key && q < root.key) root = root.left;
    else if (p > root.key && q > root.key) root = root.right;
    else return root;
  }
  return null;
}

Common bugs and edge cases

• Inserting equal keys without a policy. Decide upfront: reject duplicates, replace the value, or allow them (with left-or-right convention). Mixing policies leads to nondeterministic behavior.
• Deleting a node with two children incorrectly. Don't try to splice the children directly — replace the value with the in-order successor's value, then delete the successor. Anything else breaks the BST invariant.
• Forgetting the worst case. Plain BSTs degrade to linked lists on sorted input. If you don't control the input order, use a self-balancing tree.
• Recursive traversal on deep trees. A 100,000-node skewed tree blows the call stack. Either use an iterative traversal with an explicit stack, or use a balanced BST so depth stays O(log n).
• Comparing keys with == when they need a custom comparator. For string keys with locale-aware ordering, or for objects, you need a comparator function. Default comparison breaks down on dates, decimals, and Unicode strings.