---
title: Binary Search Trees
module: Data Structures
moduleNumber: 4
lessonNumber: 3
order: 403
summary: |
  A binary search tree keeps keys ordered so that every operation follows a
  single root-to-leaf path. We state the BST property, trace search, insert,
  successor, and all three delete cases on concrete trees, prove the inorder
  walk sorts, and note the drawback — every operation costs $O(h)$, and a
  carelessly built tree degrades to height $h = \Theta(n)$, motivating balance.
topics: [Binary Search Trees]
sources:
  - book: CLRS
    ref: "Ch. 12 — Binary Search Trees"
  - book: Skiena
    ref: "§3.4 — Binary Search Trees"
  - book: Erickson
    ref: "Ch. — Binary Search Trees"
practice:
  - title: 'Validate Binary Search Tree'
    slug: validate-binary-search-tree
    difficulty: Medium
  - title: 'Kth Smallest Element in a BST'
    slug: kth-smallest-element-in-a-bst
    difficulty: Medium
  - title: 'Insert into a Binary Search Tree'
    slug: insert-into-a-binary-search-tree
    difficulty: Medium
  - title: 'Delete Node in a BST'
    slug: delete-node-in-a-bst
    difficulty: Medium
  - title: 'Lowest Common Ancestor of a BST'
    slug: lowest-common-ancestor-of-a-binary-search-tree
    difficulty: Medium
---

A [hash table](/algorithms/data-structures/hash-tables) gives expected $O(1)$ lookups but throws away order: it cannot tell
you the smallest key, the next key after a given one, or every key in a range. A
**binary search tree** (BST) keeps those queries fast by storing keys in a
shape that _records_ their order. Each node holds a key and pointers to a left
child, a right child, and a parent; the keys are arranged so that the tree itself
is a kind of decision diagram for searching. The result is a dynamic ordered
dictionary supporting search, insert, delete, minimum, maximum, predecessor,
successor, and in-order traversal, every one of them in time proportional to
the tree's **height**.

## The binary search tree property

The arrangement is governed by one local invariant, checked at every node $x$:

> **Property (BST).** For every node $x$: if $y$ is a node in the _left_ subtree of
> $x$, then $key(y) \le key(x)$; and if $y$ is in the _right_ subtree of $x$,
> then $key(y) \ge key(x)$.

Smaller keys live to the left, larger keys to the right, _everywhere_, not just
between a node and its immediate children.[^clrs-bst] This recursive constraint is
what lets a search discard half the tree at each step.

$$
% caption: A binary search tree with smaller keys left and larger keys right
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=8mm, inner sep=0},
  level distance=12mm,
  level 1/.style={sibling distance=28mm},
  level 2/.style={sibling distance=15mm}]
  \node {6}
    child {node {3}
      child {node {2}}
      child {node {5}}
    }
    child {node {8}
      child {node {7}}
      child {node {9}}
    };
\end{tikzpicture}
$$

Reading this tree: the root is $6$; everything in its left subtree
($\set{2,3,5}$) is $\le 6$ and everything in its right subtree
($\set{7,8,9}$) is $\ge 6$, and the same holds recursively at $3$ and $8$.

## Searching

To search for a key $k$, start at the root and walk down. At each node, if $k$
equals the node's key we are done; if $k$ is smaller we go left, otherwise we go
right. Each comparison drops us one level, so the search traces a single
root-to-leaf path.

```algorithm
caption: $\textsc{Tree-Search}(x, k)$ — find key $k$ in the subtree rooted at $x$
if $x = \text{nil}$ or $k = key(x)$ then
  return $x$
if $k < key(x)$ then
  return call $\textsc{Tree-Search}(left(x), k)$ // k is in the left subtree
else
  return call $\textsc{Tree-Search}(right(x), k)$ // k is in the right subtree
```

The procedure is correct by the BST property: when $k < key(x)$, the property
guarantees $k$ cannot be in $x$'s right subtree, so discarding it loses nothing.
The search visits one node per level and runs in $O(h)$ time, where $h$ is the
height of the tree.[^skiena-bst]

$$
% caption: Searching for $k=5$. At $6$ we go left ($5<6$); at $3$ we go right ($5>3$); at
%          $5$ we stop. The path (accent) visits one node per level, and each step
%          discards an entire subtree (dashed), so the search examines just $3$ of the
%          $7$ nodes.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=8mm, inner sep=0, font=\small},
  level distance=12mm,
  level 1/.style={sibling distance=26mm},
  level 2/.style={sibling distance=14mm}, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (r) {6}
    child {node (n3) {3}
      child {node {2}}
      child {node (n5) {5}}
    }
    child {node (n8) {8}
      child {node {7}}
      child {node {9}}
    };
  % discarded subtree (muted): right subtree of 6
  \node[draw=black, dashed, very thick, minimum size=8mm, inner sep=0] at (n8) {};
  \node[draw=none, font=\scriptsize, black, align=center] at (3.9,-1.2) {5 $<$ 6:\\drop righ\/t};
  \draw[->, black] (2.9,-1.2) -- (n8.east);
  % search path highlights
  \node[draw=acc, very thick, minimum size=8mm, inner sep=0] at (r) {};
  \node[draw=acc, very thick, minimum size=8mm, inner sep=0] at (n3) {};
  \node[draw=acc, very thick, minimum size=8mm, inner sep=0] at (n5) {};
  \draw[->, acc, thick] (r) to[bend right=25] (n3);
  \draw[->, acc, thick] (n3) to[bend right=25] (n5);
\end{tikzpicture}
$$

An unsuccessful search behaves the same way. Searching for $k=4$ in this tree
compares $4 < 6$ (go left), $4 > 3$ (go right), $4 < 5$ (go left), and finds
$5$'s left child is `nil`: the key is absent, and the search reports it after
$h+1 = 3$ comparisons, never more. The `nil` that ends a failed search is not
wasted information: it marks where the key _would_ go, which is the
observation insertion is built on.

$\textsc{Tree-Minimum}$ and $\textsc{Tree-Maximum}$ are the degenerate
cases of search: follow `left` pointers until they run out to reach the smallest
key, or `right` pointers for the largest.

```algorithm
caption: $\textsc{Tree-Minimum}(x)$ and $\textsc{Tree-Maximum}(x)$
Tree-Minimum(x):
  while $left(x) \ne \text{nil}$ do
    $x \gets left(x)$ // min is the leftmost node
  return $x$
Tree-Maximum(x):
  while $right(x) \ne \text{nil}$ do
    $x \gets right(x)$ // max is the rightmost node
  return $x$
```

## Inserting

Insertion reuses the search path. To insert key $k$, walk down as if searching
for it; when the walk falls off the bottom of the tree (reaches a `nil` child),
that empty spot marks where $k$ belongs, preserving the BST property. We
attach a new leaf there, remembering the parent so we can hook it in.

```algorithm
caption: $\textsc{Tree-Insert}(T, z)$ — insert node $z$ (with $key(z)$ set) into BST $T$
$y \gets \text{nil}$ // y trails x
$x \gets root(T)$
while $x \ne \text{nil}$ do
  $y \gets x$
  if $key(z) < key(x)$ then
    $x \gets left(x)$
  else
    $x \gets right(x)$
$parent(z) \gets y$
if $y = \text{nil}$ then
  $root(T) \gets z$ // tree was empty
else if $key(z) < key(y)$ then
  $left(y) \gets z$
else
  $right(y) \gets z$
```

Like search, insertion walks one root-to-leaf path and costs $O(h)$. New keys
always enter as **leaves**, which keeps insertion simple but also lets the
tree's shape degrade, as shown below.

Tracing $\textsc{Tree-Insert}$ with $key(z) = 4$ on our running tree: $x$
starts at the root $6$ with $y = \text{nil}$. Since $4 < 6$, the trailing
pointer $y$ moves to $6$ and $x$ descends left to $3$. Since $4 > 3$, $y$ moves
to $3$ and $x$ descends right to $5$. Since $4 < 5$, $y$ moves to $5$ and $x$
descends left, to `nil`. The loop exits with $y = 5$; because $4 < 5$, the new
node becomes $5$'s left child. Three comparisons, one pointer assignment, done.

$$
% caption: Inserting $4$: the search path (accent) compares $4<6$, $4>3$, $4<5$ and falls
%          off at $5$'s empty left child — the unique spot where $4$ preserves the BST
%          property. The new node attaches there as a leaf (dashed).
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=8mm, inner sep=0, font=\small},
  >=stealth, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  \node (r) at (0,0) {6};
  \node (n3) at (-1.5,-1.2) {3};
  \node (n8) at (1.5,-1.2) {8};
  \node (n2) at (-2.2,-2.4) {2};
  \node (n5) at (-0.8,-2.4) {5};
  \node (n7) at (0.8,-2.4) {7};
  \node (n9) at (2.2,-2.4) {9};
  \draw (r)--(n3); \draw (r)--(n8);
  \draw (n3)--(n2); \draw (n3)--(n5);
  \draw (n8)--(n7); \draw (n8)--(n9);
  \node[draw=acc, dashed, very thick, fill=acc!8] (n4) at (-1.5,-3.6) {4};
  \draw[dashed, acc] (n5)--(n4);
  \node[draw=acc, very thick, minimum size=8mm, inner sep=0] at (r) {};
  \node[draw=acc, very thick, minimum size=8mm, inner sep=0] at (n3) {};
  \node[draw=acc, very thick, minimum size=8mm, inner sep=0] at (n5) {};
  \draw[->, acc, thick] (r) to[bend right=25] (n3);
  \draw[->, acc, thick] (n3) to[bend right=25] (n5);
  \node[draw=none, font=\scriptsize, black, align=center] (lbl) at (-3.4,-3.6) {new leaf};
  \draw[->, black] (lbl.east) -- (n4.west);
\end{tikzpicture}
$$

## Finding a successor

The **successor** of a node $x$ is the node with the smallest key greater than
$key(x)$, the next key in sorted order. There are two cases, and neither needs
a comparison of keys, only structure:

- If $x$ has a right subtree, the successor is the _minimum_ of that subtree:
  the smallest key still larger than $key(x)$.
- If $x$ has no right subtree, the successor is the lowest ancestor whose left
  child is also an ancestor of $x$; we climb up until we move up a _left_ link.

```algorithm
caption: $\textsc{Tree-Successor}(x)$ — next node in sorted order
if $right(x) \ne \text{nil}$ then
  return call $\textsc{Tree-Minimum}(right(x))$ // min of right subtree
$y \gets parent(x)$
while $y \ne \text{nil}$ and $x = right(y)$ do
  $x \gets y$ // climb while x is a right child
  $y \gets parent(y)$
return $y$
```

Both cases follow a single vertical path, down into the right subtree or up
through ancestors, so $\textsc{Tree-Successor}$ also runs in $O(h)$. **Predecessor**
is the mirror image (left subtree's maximum, or climb until a right link).

Trace both cases on the running tree. For $x = 6$ (case 1): $right(6) = 8$ is
non-`nil`, so we return $\textsc{Tree-Minimum}$ of the subtree at $8$: descend
left from $8$ to $7$, and $7$ has no left child, so the successor is $7$.
Correct: $7$ is the smallest key exceeding $6$. For $x = 5$ (case 2): $5$ has
no right subtree, so we climb. First iteration: $y = 3$ and $5 = right(3)$, so
$x \gets 3$, $y \gets 6$. Second test: $3 = left(6)$, not a right child, so the
loop stops and returns $6$, the first ancestor reached by moving _up-and-right_,
which is precisely the smallest key greater than everything in $3$'s subtree.
The climb can also run off the top: for $x = 9$ the loop ascends $9 \to 8 \to 6$
(each a right child of its parent) and exits with $y = \text{nil}$; $9$ is the
maximum and has no successor. A predecessor trace mirrors this: for $x = 7$,
which has no left subtree, we climb while $x$ is a _left_ child ($7 = left(8)$,
so $x \gets 8$), then stop because $8 = right(6)$, returning $6$.

$$
% caption: The two successor cases. Left: $6$ has a right subtree, so its successor is
%          that subtree's minimum, $7$ (descend left from $8$). Right: $5$ has no right
%          subtree, so climb until moving up a left link — $5\to3\to6$ — giving successor
%          $6$.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0, font=\small},
  level distance=11mm,
  level 1/.style={sibling distance=20mm},
  level 2/.style={sibling distance=11mm}, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % LEFT panel: right-subtree-min case, x=6
  \begin{scope}
    \node (r) {6}
      child {node {3}
        child {node {2}}
        child {node {5}}
      }
      child {node (e8) {8}
        child {node (e7) {7}}
        child {node {9}}
      };
    \node[draw=acc, very thick, minimum size=7mm, inner sep=0] at (r) {};
    \node[draw=acc, very thick, minimum size=7mm, inner sep=0] at (e7) {};
    \draw[->, acc, thick] (r) to[bend left=25] (e8);
    \draw[->, acc, thick] (e8) to[bend left=25] (e7);
  \end{scope}
  % RIGHT panel: climb case, x=5
  \begin{scope}[xshift=6.4cm]
    \node (q) {6}
      child {node (q3) {3}
        child {node {2}}
        child {node (q5) {5}}
      }
      child {node {8}
        child {node {7}}
        child {node {9}}
      };
    \node[draw=acc, very thick, minimum size=7mm, inner sep=0] at (q5) {};
    \node[draw=acc, very thick, minimum size=7mm, inner sep=0] at (q) {};
    \draw[->, acc, thick] (q5) to[bend left=28] (q3);
    \draw[->, acc, thick] (q3) to[bend left=28] (q);
  \end{scope}
\end{tikzpicture}
$$

## Deleting a node

Deletion is the one operation that needs care, because removing an internal node
leaves a hole that must be filled without disturbing the BST property. There are
three cases, in increasing difficulty:

1. $z$ has **no children**: just detach it from its parent.
2. $z$ has **one child**: splice that child into $z$'s position.
3. $z$ has **two children**: $z$'s successor $y$ is the minimum of its right
   subtree, so $y$ has no left child. Move $y$ into $z$'s position; if $y$ was
   not $z$'s direct child, first replace $y$ by its own right child.

All three reduce to a single primitive, $\textsc{Transplant}$, which replaces the
subtree rooted at $u$ with the subtree rooted at $v$:

```algorithm
caption: $\textsc{Transplant}(T, u, v)$ — put subtree $v$ where subtree $u$ was
if $parent(u) = \text{nil}$ then
  $root(T) \gets v$
else if $u = left(parent(u))$ then
  $left(parent(u)) \gets v$
else
  $right(parent(u)) \gets v$
if $v \ne \text{nil}$ then
  $parent(v) \gets parent(u)$
```

```algorithm
caption: $\textsc{Tree-Delete}(T, z)$ — remove node $z$ from the BST
if $left(z) = \text{nil}$ then
  call $\textsc{Transplant}(T, z, right(z))$ // lift the right child
else if $right(z) = \text{nil}$ then
  call $\textsc{Transplant}(T, z, left(z))$ // lift the left child
else
  $y \gets$ call $\textsc{Tree-Minimum}(right(z))$ // successor, no left child
  if $parent(y) \ne z$ then
    call $\textsc{Transplant}(T, y, right(y))$ // detach y, lift its right child
    $right(y) \gets right(z)$
    $parent(right(y)) \gets y$
  call $\textsc{Transplant}(T, z, y)$ // y into z's slot
  $left(y) \gets left(z)$
  $parent(left(y)) \gets y$
```

The first two cases are pure pointer splices, and both are handled by the same
two branches of $\textsc{Tree-Delete}$: when $left(z)$ is `nil` we transplant
$right(z)$ into $z$'s place (this covers the leaf case too, transplanting
`nil`), and symmetrically when $right(z)$ is `nil`. Concretely, in the tree
below, deleting the leaf $2$ calls $\textsc{Transplant}(T, 2, \text{nil})$:
since $2 = left(3)$, the assignment $left(3) \gets \text{nil}$ detaches it and
nothing else moves. Deleting $8$, which has only the child $9$, calls
$\textsc{Transplant}(T, 8, 9)$: since $8 = right(6)$, we set
$right(6) \gets 9$ and $parent(9) \gets 6$, and $9$ rises one level with its
subtree intact; every key in it is still $> 6$, so the BST property holds.

$$
% caption: The two easy delete cases. Top: the leaf $2$ (shaded) is detached by pointing
%          its parent's child link at nil. Bottom: $8$ has one child, so that child ($9$,
%          accent) is spliced into $8$'s position, carrying its whole subtree with it.
\begin{tikzpicture}[n/.style={circle, draw, minimum size=7mm, font=\small, inner sep=0pt}, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % row 1: delete leaf 2
  \node[n] (a) at (0,0) {6};
  \node[n] (a3) at (-1.3,-1.1) {3}; \node[n] (a8) at (1.3,-1.1) {8};
  \node[n, fill=black!15] (a2) at (-1.9,-2.2) {2}; \node[n] (a5) at (-0.7,-2.2) {5};
  \node[n] (a9) at (1.9,-2.2) {9};
  \draw (a)--(a3); \draw (a)--(a8); \draw (a3)--(a2); \draw (a3)--(a5); \draw (a8)--(a9);
  \node[font=\scriptsize] at (3.2,-0.75) {delete 2};
  \draw[->, thick] (2.5,-1.1) -- (3.9,-1.1);
  \node[n] (b) at (6.5,0) {6};
  \node[n] (b3) at (5.2,-1.1) {3}; \node[n] (b8) at (7.8,-1.1) {8};
  \node[n] (b5) at (5.8,-2.2) {5}; \node[n] (b9) at (8.4,-2.2) {9};
  \draw (b)--(b3); \draw (b)--(b8); \draw (b3)--(b5); \draw (b8)--(b9);
  % row 2: delete one-child node 8
  \begin{scope}[yshift=-3.4cm]
    \node[n] (c) at (0,0) {6};
    \node[n] (c3) at (-1.3,-1.1) {3}; \node[n, fill=black!15] (c8) at (1.3,-1.1) {8};
    \node[n] (c2) at (-1.9,-2.2) {2}; \node[n] (c5) at (-0.7,-2.2) {5};
    \node[n, fill=acc!16] (c9) at (1.9,-2.2) {9};
    \draw (c)--(c3); \draw (c)--(c8); \draw (c3)--(c2); \draw (c3)--(c5); \draw (c8)--(c9);
    \node[font=\scriptsize] at (3.2,-0.75) {delete 8};
    \draw[->, thick] (2.5,-1.1) -- (3.9,-1.1);
    \node[n] (d) at (6.5,0) {6};
    \node[n] (d3) at (5.2,-1.1) {3}; \node[n, fill=acc!16] (d9) at (7.8,-1.1) {9};
    \node[n] (d2) at (4.6,-2.2) {2}; \node[n] (d5) at (5.8,-2.2) {5};
    \draw (d)--(d3); \draw (d)--(d9); \draw (d3)--(d2); \draw (d3)--(d5);
  \end{scope}
\end{tikzpicture}
$$

The two-child case is the subtle one. Replacing $z$ by its successor keeps every
key in $z$'s left subtree below the new root and every key in the right subtree
above it, so the ordering survives:

$$
% caption: Deleting a node with two children: its successor (the minimum of the right
%          subtree, here $6$) takes its place, and the successor's own right child ($7$)
%          fills the slot it vacated.
\begin{tikzpicture}[n/.style={circle, draw, minimum size=7mm, font=\small, inner sep=0pt}, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[n, fill=black!15] (a) at (0,0) {5};
  \node[n] (a3) at (-1.3,-1.2) {3}; \node[n] (a8) at (1.3,-1.2) {8};
  \node[n] (a2) at (-1.9,-2.4) {2}; \node[n] (a4) at (-0.7,-2.4) {4};
  \node[n, fill=acc!16] (a6) at (0.7,-2.4) {6}; \node[n] (a9) at (1.9,-2.4) {9};
  \node[n] (a7) at (1.1,-3.5) {7};
  \draw (a)--(a3); \draw (a)--(a8); \draw (a3)--(a2); \draw (a3)--(a4); \draw (a8)--(a6); \draw (a8)--(a9); \draw (a6)--(a7);
  \node[font=\scriptsize] at (3.3,-1.55) {delete $5$};
  \draw[->, thick] (2.5,-1.9) -- (3.9,-1.9);
  \node[n, fill=acc!16] (b) at (6.5,0) {6};
  \node[n] (b3) at (5.2,-1.2) {3}; \node[n] (b8) at (7.8,-1.2) {8};
  \node[n] (b2) at (4.6,-2.4) {2}; \node[n] (b4) at (5.8,-2.4) {4};
  \node[n] (b7) at (7.2,-2.4) {7}; \node[n] (b9) at (8.4,-2.4) {9};
  \draw (b)--(b3); \draw (b)--(b8); \draw (b3)--(b2); \draw (b3)--(b4); \draw (b8)--(b7); \draw (b8)--(b9);
\end{tikzpicture}
$$

Follow the pointer surgery step by step. We delete $z = 5$, the root. Both
children exist, so the third branch runs: $y \gets \textsc{Tree-Minimum}(8) = 6$
(from $8$, one step left, then no further). Here $parent(y) = 8 \ne z$, so the
inner fix-up fires first: $\textsc{Transplant}(T, 6, 7)$ lifts $6$'s right
child $7$ into $6$'s old slot ($left(8) \gets 7$), then $right(6) \gets 8$ and
$parent(8) \gets 6$ hand $z$'s entire right subtree to $y$. Now
$\textsc{Transplant}(T, 5, 6)$ makes $6$ the root, and $left(6) \gets 3$,
$parent(3) \gets 6$ attach the untouched left subtree. The result is the tree
on the right: $6$ sits where $5$ was, $7$ sits where $6$ was, and every
ordering relation still holds because $6$ was the smallest key in the right
subtree: everything remaining there is larger, and everything on the left was
already smaller. When the successor _is_ $z$'s direct child ($parent(y) = z$),
the inner fix-up is skipped: $y$'s right subtree is already in the correct
position relative to $y$, and the final transplant alone suffices. Why the
successor and not some other key? Only $z$'s successor or predecessor can
replace $z$ without reordering: the replacement must be larger than all of
$z$'s left subtree and smaller than all of its right subtree except itself, and
the successor (minimum of the right subtree) is one of exactly two keys with
that property.

Each branch does a constant amount of pointer surgery plus at most one
$\textsc{Tree-Minimum}$ call, so $\textsc{Tree-Delete}$ runs in $O(h)$ like the rest.

## The order is already there: inorder walk

Because the BST property sorts keys left-to-right at every node, visiting the
tree **in order** — left subtree, then the node, then right subtree — emits the
keys in increasing order.[^erickson-bst]

```algorithm
caption: $\textsc{Inorder-Walk}(x)$ — print the subtree at $x$ in sorted order
if $x \ne \text{nil}$ then
  call $\textsc{Inorder-Walk}(left(x))$ // smaller keys first
  print $key(x)$
  call $\textsc{Inorder-Walk}(right(x))$ // then larger keys
```

> **Claim.** $\textsc{Inorder-Walk}$ on a BST prints the keys in nondecreasing order.

> **Proof (strong induction on subtree size $n$).** _Base case_: a subtree of
> size $0$ is `nil`; the walk prints nothing, which is vacuously sorted.
> _Inductive step_: let the claim hold for all subtrees of size $< n$, and let
> $x$ root a subtree of size $n \ge 1$ whose left subtree has $k$ nodes, so the
> right subtree has $n - 1 - k$. Both are strictly smaller than $n$, so the
> hypothesis applies to each. The walk first recurses on $left(x)$, printing its
> $k$ keys in nondecreasing order; by the BST property each of those keys is
> $\le key(x)$. It then prints $key(x)$. It then recurses on $right(x)$,
> printing its $n-1-k$ keys in nondecreasing order, each $\ge key(x)$ by the BST
> property. The concatenation of a sorted block of keys $\le key(x)$, then
> $key(x)$ itself, then a sorted block of keys $\ge key(x)$ is nondecreasing,
> and it contains all $n$ keys exactly once. $\qed$

The walk visits each of $n$ nodes once, so it runs in $\Theta(n)$ time. This
gives a clean way to read out a sorted sequence, and shows that a BST is, in
effect, a dynamic sorted list you can also splice into and search.

## The catch: height is everything

Every operation above costs $O(h)$. So the BST is fast exactly when $h$ is
small. The **best case** is a _balanced_ tree, where the two subtrees of each
node have nearly equal size; then $h = \Theta(\log n)$ and every operation is
$\Theta(\log n)$.

The **worst case** is a disaster. Suppose we insert keys in _sorted_ order:
$1, 2, 3, \dots, n$. Each new key is larger than everything present, so it walks
all the way right and attaches as the rightmost leaf. The tree degenerates into a
single descending path, a glorified linked list:

$$
% caption: Sorted insertions degenerate a BST into a path of height $n-1$
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0},
  level distance=9mm,
  level 1/.style={sibling distance=10mm}]
  \node {1}
    child[missing]
    child {node {2}
      child[missing]
      child {node {3}
        child[missing]
        child {node {4}
          child[missing]
          child {node {5}}
        }
      }
    };
\end{tikzpicture}
$$

Now $h = n - 1$, and search, insert, and successor all degrade to $\Theta(n)$,
no better than scanning an unsorted array.[^clrs-height] The very flexibility that made
insertion easy (new keys land as leaves wherever the path takes them) lets an
unlucky or adversarial insertion order ruin the shape. And sorted input is not a
contrived adversary: it is one of the most common inputs in practice: keys read
from a sorted file, timestamps arriving in order, sequential IDs from a database.
Reverse-sorted input produces the mirror-image left path, and nearly-sorted
input produces a tree that is nearly a path. Building a BST naively from data
that "happens to be" ordered is a classic performance bug: the code is correct,
the tests pass on small shuffled inputs, and production slows to a crawl.

How bad is a _typical_ tree, as opposed to a worst-case one? There is a
positive result here, with an important caveat about what "typical" means. Call
a BST **randomly built** if it results from inserting $n$ distinct keys in
uniformly random order into an empty tree.

> **Theorem (expected height of a randomly built BST).** The expected height of
> a randomly built binary search tree on $n$ distinct keys is $O(\log n)$.[^clrs-random]

So if insertion order were genuinely random, plain BSTs would be fine on
average: the expected height is within a constant factor of the optimal
$\log_2 n$ (the constant in the known bounds is roughly $3$). The caveats:
first, the theorem randomizes over insertion _orders_, not over tree shapes;
it is a statement about a random process, and real inputs (sorted, nearly
sorted, adversarial) need not look anything like a random permutation. Second,
the guarantee is only in expectation and says nothing once **deletions** mix
into the workload; the classical analysis covers insertion-only sequences.
Randomized structures such as treaps enforce the random-order behavior
regardless of the actual arrival order, which is one principled fix. The
other is to enforce balance structurally.

This is the central tension of binary search trees:

> **Remark (BST height tension).** A BST is only as good as it is _short_. Operations are $O(h)$, and $h$ ranges
> from $\Theta(\log n)$ down to $\Theta(n)$, depending
> entirely on the order of insertions.

We cannot control the order in which keys arrive. So the fix is to make the tree
_rebalance itself_ as keys come and go, forcing $h = O(\log n)$ no matter what.
Randomized BSTs (and treaps) achieve $\Theta(\log n)$ height _in expectation_;
[balanced search trees](/algorithms/data-structures/balanced-trees) — red-black trees, [AVL trees](/algorithms/data-structures/avl-trees), B-trees — guarantee
$O(\log n)$ height in the _worst case_ by maintaining extra structural
invariants and repairing them after each update. That repair machinery is the
subject of the next lesson.

::impl{algo="binary_search_tree"}

## Augmenting the tree

A BST is not only a sorted set; once you hang extra information on each node, the
same $O(h)$ walk answers much richer queries. The general method, from
CLRS's chapter on **augmenting data structures**, is to store a small summary in
each node that can be recomputed from a node and its two children in $O(1)$, so
rotations still repair it cheaply.

**Order-statistic trees.** Store in each node the _size_ of its subtree. Then two
new queries run in $O(h)$: **select$(i)$**, find the $i$-th smallest key, and
**rank$(x)$**, count how many keys are $\le x$. Select descends by comparing $i$
against the left subtree's size; rank accumulates left-subtree sizes along the
search path. This augmentation is what the LeetCode problem _Kth Smallest Element in a
BST_ wants, and what a balanced order-statistic tree gives in $O(\log n)$, the
LeetCode _Count of Smaller Numbers After Self_ is the same augmentation applied
online. As a concrete trace: in a tree holding $\{1,3,5,7,9\}$ with $5$ at the
root (left subtree size $2$), $\textbf{select}(4)$ sees $i = 4 > 2 + 1$, subtracts
the $3$ keys at-or-left of the root, and recurses for the $1$st smallest in the
right subtree $\{7, 9\}$, landing on $7$.

**Interval and other summaries.** Store the maximum endpoint in each subtree and
the tree answers "does any stored interval overlap $[a,b]$?" in $O(\log n)$, the
interval tree, taken up in
[Spatial Data Structures](/algorithms/data-structures/spatial-data-structures).
Store subtree sums and you get the ordered analogue of a
[Fenwick tree](/algorithms/data-structures/fenwick-and-segment-trees). The lesson
is that a self-balancing BST is a _substrate_: rank/select, dynamic order
statistics, and stabbing queries are all one augmentation away, which is why
balanced BSTs, not hash tables, back the ordered-map type (`std::map`,
Java `TreeMap`) in standard libraries.[^btb-bst]

## Takeaways

- A **binary search tree** stores keys under the **BST property** (left subtree
  $\le$ node $\le$ right subtree, recursively), so searching follows one
  root-to-leaf path.
- **Search, insert, minimum, maximum, successor, predecessor** all walk a single
  vertical path and cost $O(h)$; new keys enter as **leaves**.
- **Delete** has three cases — leaf, one child, two children — all built on the
  $\textsc{Transplant}$ splice; the two-child case moves the **successor** into
  the deleted node's place, which preserves ordering because the successor is
  the minimum of the right subtree.
- An **inorder walk** emits the keys in sorted order in $\Theta(n)$ time; the
  order is baked into the shape.
- Performance hinges entirely on **height**: $\Theta(\log n)$ when balanced,
  but $\Theta(n)$ for a degenerate (e.g. sorted-insertion) tree. A **randomly
  built** BST has expected height $O(\log n)$, but that assumes random insertion
  order and no deletions; real inputs offer no such promise.
- Because we cannot control insertion order, we need trees that **rebalance
  themselves** to guarantee $h = O(\log n)$, the motivation for balanced search
  trees.

[^clrs-bst]: **CLRS**, Ch. 12 — Binary Search Trees (§12.1): the BST property as a recursive ordering invariant.
[^skiena-bst]: **Skiena**, §3.4 — Binary Search Trees: search along a single root-to-leaf path in $O(h)$ time.
[^erickson-bst]: **Erickson**, Ch. — Binary Search Trees: an inorder traversal emits the keys in sorted order.
[^clrs-height]: **CLRS**, Ch. 12 — Binary Search Trees (§12.4): operations cost $O(h)$, degrading to $\Theta(n)$ for an unbalanced tree.
[^clrs-random]: **CLRS**, Ch. 12 — Binary Search Trees (§12.4, Theorem 12.4): a randomly built BST on $n$ distinct keys has expected height $O(\lg n)$; the analysis assumes insertions only, in uniformly random order.
[^btb-bst]: **CLRS**, Ch. 14 — Augmenting Data Structures: order-statistic trees (subtree sizes for select/rank) and interval trees (subtree max endpoint), and the general rule for augmenting a red-black tree with recomputable summaries.