# Binary Search Trees — Part 1: The Pattern

A binary search tree keeps an ordering invariant: **everything in a node's left subtree is smaller, everything in its right subtree is larger**. That turns search, insert and delete into a single walk down one path, O(h) for height h, and makes an **inorder traversal produce sorted order**. Interview questions test whether you can exploit that invariant (skip half the tree at every node) and whether you validate it correctly.

![A BST with the valid range of each node](diagrams/01-bst-ranges.svg)

## 1. Operations

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function search(root: TreeNode | null, target: number): TreeNode | null {
  let node = root;
  while (node && node.val !== target) node = target < node.val ? node.left : node.right;
  return node;
}

function insert(root: TreeNode | null, val: number): TreeNode {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

function isValid(node: TreeNode | null, low = -Infinity, high = Infinity): boolean {
  if (!node) return true;
  if (!(low < node.val && node.val < high)) return false;
  return isValid(node.left, low, node.val) && isValid(node.right, node.val, high);
}

function bstOps(level: (number | null)[], x: number): any[] {
  const root = _tree(level);
  insert(root, x);
  return [search(root, x) !== null, isValid(root), _level(root)];
}
```

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def search(root, target):
    node = root
    while node and node.val != target:
        node = node.left if target < node.val else node.right
    return node

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def is_valid(node, low=float("-inf"), high=float("inf")):
    if not node:
        return True
    if not (low < node.val < high):
        return False
    return is_valid(node.left, low, node.val) and is_valid(node.right, node.val, high)

def bst_ops(level, x):
    root = _tree(level)
    insert(root, x)
    return [search(root, x) is not None, is_valid(root), _level(root)]
```

| Operation | Balanced BST | Degenerate (sorted inserts) |
|---|---|---|
| search / insert / delete | O(log n) | O(n) |
| min / max | O(log n): walk left/right | O(n) |
| inorder (sorted) iteration | O(n) | O(n) |
| k-th smallest | O(h + k), or O(log n) with subtree sizes | O(n) |

**Delete** has three cases: a leaf (remove it), one child (splice the child up), two children (replace the value with the **inorder successor**, the minimum of the right subtree, then delete that successor).

## 2. Validating a BST Correctly

Checking only `left.val < node.val < right.val` is **wrong**: a node deep in the left subtree must also be smaller than every ancestor it sits to the left of. Pass a **valid range** `(low, high)` down the tree: going left tightens `high` to the parent's value, going right tightens `low`. Equivalently, an inorder traversal must be strictly increasing.

## 3. Using the Invariant

- **Search-like problems** (LCA in a BST, closest value, floor/ceiling): at each node decide left or right, so you only walk one path.
- **Order statistics** (k-th smallest, two-sum in BST, recover swapped nodes): use inorder traversal, often iteratively so you can stop early.
- **Construction** (sorted array → balanced BST): take the middle element as root, recurse on halves.

## 4. Balanced BSTs and Sorted Containers

Real systems keep BSTs balanced with rotations: **AVL trees** (strict height balance) or **red-black trees** (looser, fewer rotations). You'll rarely implement one in an interview, but know what your language provides:

| Language | Ordered set / map |
|---|---|
| Python | none built in; `bisect` on a sorted list (O(n) insert), or `sortedcontainers.SortedList` |
| JavaScript / TypeScript | none built in; a sorted array + binary search, or a library |
| C# | `SortedSet<T>`, `SortedDictionary<K,V>` (red-black trees), `SortedList<K,V>` (array) |
| Java | `TreeSet`, `TreeMap` |

## Under the Hood: Why Databases Use B-Trees, Not BSTs

A BST node holds one key, so a million keys need about 20 levels, which means up to 20 random disk reads per lookup. A **B-tree** node holds hundreds of keys (one disk page), so the same million keys fit in about 3 levels. Same invariant, wider nodes: see `databases/indexing-storage/02-b_tree`.

## Common Pitfalls

1. **Validating only parent–child pairs** instead of the full ancestor range.
2. **Using `int` min/max as sentinels** when node values can equal them; use `None`/`null` or ±infinity.
3. **Duplicates:** decide (and say) whether they go left, right, or are disallowed.
4. **Assuming O(log n)** for an unbalanced BST; sorted inserts make it a linked list.
5. **Forgetting to return the (possibly new) root** from recursive insert/delete.

## Quick Reference

```text
search: while node and node.val != x: node = left if x < node.val else right
validate: f(node, low, high): low < val < high; left gets (low, val), right gets (val, high)
inorder of a BST = sorted order · delete with 2 children → inorder successor
O(h): log n balanced, n degenerate
```