---
title: Tries & Prefix Trees
module: Sequences & Strings
moduleNumber: 5
lessonNumber: 7
order: 507
summary: |
  A **trie** stores a set of strings in a tree keyed by _characters_, so that
  insert, search, delete, and prefix-test all run in $O(L)$ time — the length
  of the key, _independent of how many keys are stored_. Shared prefixes are
  stored once, which makes tries the natural structure for autocomplete,
  wildcard dictionaries, board word-search, and — over the alphabet $\{0,1\}$
  — the maximum-XOR-pair problem. Radix (Patricia) trees compress the chains.
topics: [Strings]
sources:
  - book: Skiena
    ref: "§ — String Data Structures"
  - book: Erickson
    ref: "Ch. — Data Structures"
  - book: CLRS
    ref: "Prob. 12-2 — Radix Trees"
practice:
  - title: 'Implement Trie (Prefix Tree)'
    slug: implement-trie-prefix-tree
    difficulty: Medium
  - title: 'Design Add and Search Words Data Structure'
    slug: design-add-and-search-words-data-structure
    difficulty: Medium
  - title: 'Word Search II'
    slug: word-search-ii
    difficulty: Hard
  - title: 'Maximum XOR of Two Numbers in an Array'
    slug: maximum-xor-of-two-numbers-in-an-array
    difficulty: Medium
---

A balanced search tree gives us $O(\log n)$ lookups by comparing whole keys to
each other. But when the keys are _strings_, a single comparison is not $O(1)$:
deciding whether `"international"` precedes `"internet"` already costs five
character comparisons, so a BST of $n$ strings of length $L$ really spends
$O(L \log n)$ per operation. Worse, the [BST](/algorithms/data-structures/binary-search-trees) throws away an obvious source of
structure, namely that `"intern"`, `"internet"`, and `"international"` all _share a
prefix_, and re-examines those shared characters on every descent.

A **trie** (the middle syllable of re<mark>trie</mark>val, usually pronounced
"try") exploits that
structure. Instead of comparing keys against each other, it routes each key
_one character at a time_ down a tree whose edges are labeled by characters. A
root-to-node path spells a prefix; following the characters of a key leads to
the unique node that key reaches. Lookup costs $O(L)$, where the work depends only on
the key being searched for, **never on $n$**, the number of stored keys.[^skiena-trie]

## The structure

> **Definition (trie).** A _trie_ over an alphabet $\Sigma$ is a rooted tree in
> which every edge is labeled by a character of $\Sigma$, the edges leaving any
> node carry distinct labels, and the concatenation of labels on the path from
> the root to a node $v$ is the _prefix_ represented by $v$. A boolean flag
> $isEnd(v)$ marks the nodes whose prefix is a complete stored key.

The root represents the empty prefix. The bookkeeping is two-level: a node can
exist purely as an interior waypoint (a prefix of some longer key) yet _not_ be a
key itself. In the word set $\{\texttt{to}, \texttt{tea}, \texttt{ted}\}$ the node
at path `t` exists but is not a stored word, so its $isEnd$ is false; the nodes at
`to`, `tea`, and `ted` have $isEnd = \text{true}$. The flag is what lets a stored
word be a prefix of another stored word: with both `in` and `inn` present, the
node at `in` is simultaneously a terminal (its own flag is true) and an interior
waypoint on the path to `inn`. Without the flag, the structure could not tell
"`in` is a word" apart from "`in` is merely a prefix of `inn`".

Each node needs a way to find a child by character. Two standard choices:

- **Array children.** A fixed array of $|\Sigma|$ pointers per node (e.g. 26 for
  lowercase letters, or `children[2]` for a binary trie). Child lookup is a single
  $O(1)$ index, at the cost of $|\Sigma|$ slots per node whether used or not.
- **[Hash-map](/algorithms/data-structures/hash-tables) children.** A `char → node` map per node, so a node stores only the
  children it actually has. Smaller for sparse, large alphabets (Unicode), with a
  small constant-factor hashing overhead.

## Operations: all $O(L)$

Insertion walks down from the root, _creating_ a child node whenever the needed
edge is missing, and sets $isEnd$ on the final node. Search walks the same path
but never creates; it fails the moment a needed edge is absent.

```algorithm
caption: $\textsc{Insert}(T, w)$ — add word $w = w_1 w_2 \dots w_L$
$x \gets root(T)$
for $i \gets 1$ to $L$ do
  $c \gets w_i$
  if $child(x, c) = \text{nil}$ then
    $child(x, c) \gets \textsc{NewNode}()$
  $x \gets child(x, c)$
$isEnd(x) \gets \text{true}$
```

```algorithm
caption: $\textsc{Search}(T, w)$ — is $w$ a stored key?
$x \gets root(T)$
for $i \gets 1$ to $L$ do
  $c \gets w_i$
  if $child(x, c) = \text{nil}$ then
    return false
  $x \gets child(x, c)$
return $isEnd(x)$
```

Each loop runs $L$ times and does $O(1)$ work per character (one indexed slot or
one hash probe), so **insert, search, and the prefix test all run in $O(L)$**.
`startsWith(p)` is identical to $\textsc{Search}$ except it returns _true_ as soon as
the path for $p$ exists, ignoring $isEnd$, because any node on a valid path
witnesses that $p$ is a prefix of some stored key.

Correctness rests on one property that every operation preserves:

> **Invariant.** At all times, for every node $v$ the root-to-$v$ path spells a
> distinct string, and $isEnd(v)$ is true exactly when that string has been
> inserted and not deleted. Since edges out of a node carry distinct labels,
> each string reaches _at most one_ node, so $\textsc{Search}$ ends at the unique
> candidate node and the flag it reads cannot belong to any other key.

$\textsc{Insert}$ preserves the invariant because it only ever creates the node
its own path requires and flags only its final node; it cannot disturb any other
key's path, which is why a trie needs no rebalancing — the shape is determined by
the key set alone, not by insertion order.

> **Remark (The decisive contrast).** A balanced BST of strings pays
> $O(L \log n)$ per operation: $\log n$ comparisons, each up to $L$ characters.
> A hash set of strings pays $O(L)$ to hash the key but loses all ordering and
> prefix structure. A trie pays $O(L)$ _and_ keeps the keys in sorted order and
> answers prefix queries directly. The $\log n$ factor simply disappears: trie
> cost is independent of $n$.

$$
% caption: Cost of the three string-dictionary structures per operation on $n$ keys of
%          length $L$. The trie alone drops the $\log n$ factor and answers prefix queries
%          directly; the hash set is $O(L)$ but unordered
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \node[font=\footnotesize] at (2.0,0.4) {searc\/h};
  \node[font=\footnotesize] at (4.0,0.4) {ordered?};
  \node[font=\footnotesize] at (6.2,0.4) {pref\/ix query?};
  \draw[thick] (-1.4,0.1) -- (7.3,0.1);
  \node[font=\footnotesize] at (-0.7,-0.4) {BST};
  \node[font=\footnotesize] at (2.0,-0.4) {$O(L\log n)$};
  \node[font=\footnotesize] at (4.0,-0.4) {yes};
  \node[font=\footnotesize] at (6.2,-0.4) {no};
  \node[font=\footnotesize] at (-0.7,-1.0) {hash set};
  \node[font=\footnotesize] at (2.0,-1.0) {$O(L)$};
  \node[font=\footnotesize] at (4.0,-1.0) {no};
  \node[font=\footnotesize] at (6.2,-1.0) {no};
  \node[font=\footnotesize, text=acc] at (-0.7,-1.6) {trie};
  \node[font=\footnotesize, text=acc] at (2.0,-1.6) {$O(L)$};
  \node[font=\footnotesize, text=acc] at (4.0,-1.6) {yes};
  \node[font=\footnotesize, text=acc] at (6.2,-1.6) {yes};
  \draw[acc, thick] (-1.4,-1.3) rectangle (7.3,-1.9);
\end{tikzpicture}
$$

$$
% caption: A trie over \{to, tea, ted, ten, in, inn\}; shared prefixes stored once, lookup
%          is $O(L)$
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6mm, inner sep=0, font=\small},
  acc/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=6mm, inner sep=0, font=\small},
  level distance=11mm,
  edgelbl/.style={draw=none, font=\footnotesize, fill=none},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (root) {};
  \node[draw=none, fill=none, font=\scriptsize, text=black] at ([xshift=9mm]root.east) {ro\/ot};
  % t branch
  \node (t)  [below left=11mm and 16mm of root] {};
  \node (to) [below left=11mm and 9mm of t, acc] {};
  \node (te) [below right=11mm and 5mm of t] {};
  \node (tea)[below left=11mm and 5mm of te, acc] {};
  \node (ted)[below=11mm of te, acc] {};
  \node (ten)[below right=11mm and 5mm of te, acc] {};
  % i branch
  \node (i)  [below right=11mm and 16mm of root] {};
  \node (in) [below=11mm of i, acc] {};
  \node (inn)[below=11mm of in, acc] {};
  \draw[->] (root) -- node[edgelbl,left] {t} (t);
  \draw[->] (root) -- node[edgelbl,right] {i} (i);
  \draw[->] (t) -- node[edgelbl,left] {o} (to);
  \draw[->] (t) -- node[edgelbl,right] {e} (te);
  \draw[->] (te) -- node[edgelbl,left] {a} (tea);
  \draw[->] (te) -- node[edgelbl,left] {d} (ted);
  \draw[->] (te) -- node[edgelbl,right] {n} (ten);
  \draw[->] (i) -- node[edgelbl,right] {n} (in);
  \draw[->] (in) -- node[edgelbl,right] {n} (inn);
\end{tikzpicture}
$$

The blue nodes are the six stored words; the white interior nodes (`t`, `te`,
`i`) are prefixes shared among them and stored exactly once. Looking up `ten`
visits three edges regardless of whether the trie holds six words or six million.

### A build trace: counting created nodes

To see the sharing, build that trie from scratch, one insert at a
time. Each insert walks its word and creates a node only where the path runs out:

1. **Insert `tea`** into the empty trie. No edges exist, so all three characters
   miss: create nodes for `t`, `te`, `tea` (**3 new nodes**); flag `tea`.
2. **Insert `ted`.** The walk reuses `t` and `te` (two existing edges), then `d`
   misses: **1 new node**.
3. **Insert `to`.** Reuses `t`; `o` misses: **1 new node**.
4. **Insert `in`.** Nothing under `i` exists: **2 new nodes**.
5. **Insert `inn`.** Reuses `i` and `in`; the second `n` misses: **1 new node**.
6. **Insert `ten`.** Reuses `t` and `te`; `n` misses: **1 new node**.

The six words contain $3+3+2+2+3+3 = 16$ characters, but the finished trie has
only **9 nodes** besides the root, because the 7 characters that ride shared
prefixes cost nothing. The more the key set overlaps, the wider that gap grows;
inserting `tent` next would cost exactly one node.

$$
% caption: Inserting \texttt{ten} into the trie of \{to, tea, ted\}: the walk reuses the
%          existing $t$ and $e$ edges (accent) and creates exactly one node for the final
%          \texttt{n}. Shared prefixes make later inserts cheap
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6mm, inner sep=0, font=\small},
  acc/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=6mm, inner sep=0, font=\small},
  newnode/.style={circle, draw=acc, very thick, dashed, fill=acc!8, minimum size=6mm, inner sep=0, font=\small},
  edgelbl/.style={draw=none, fill=none, font=\footnotesize},
  accedge/.style={draw=acc, thick, ->},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % ---- before ----
  \node (r1) at (0,0) {};
  \node (t1)  [below=11mm of r1] {};
  \node (to1) [below left=11mm and 10mm of t1, acc] {};
  \node (te1) [below right=11mm and 6mm of t1] {};
  \node (tea1)[below left=11mm and 6mm of te1, acc] {};
  \node (ted1)[below right=11mm and 6mm of te1, acc] {};
  \draw[->] (r1) -- node[edgelbl,left] {t} (t1);
  \draw[->] (t1) -- node[edgelbl,left] {o} (to1);
  \draw[->] (t1) -- node[edgelbl,right] {e} (te1);
  \draw[->] (te1) -- node[edgelbl,left] {a} (tea1);
  \draw[->] (te1) -- node[edgelbl,right] {d} (ted1);
  \node[draw=none, fill=none, font=\footnotesize, text=black] at (0,1.0) {before};
  % ---- after ----
  \node (r2) at (6.6,0) {};
  \node (t2)  [below=11mm of r2] {};
  \node (to2) [below left=11mm and 12mm of t2, acc] {};
  \node (te2) [below right=11mm and 6mm of t2] {};
  \node (tea2)[below left=11mm and 10mm of te2, acc] {};
  \node (ted2)[below=11mm of te2, acc] {};
  \node (ten2)[below right=11mm and 10mm of te2, newnode] {};
  \draw[accedge] (r2) -- node[edgelbl,left] {t} (t2);
  \draw[->] (t2) -- node[edgelbl,left] {o} (to2);
  \draw[accedge] (t2) -- node[edgelbl,right] {e} (te2);
  \draw[->] (te2) -- node[edgelbl,left] {a} (tea2);
  \draw[->] (te2) -- node[edgelbl,left] {d} (ted2);
  \draw[accedge] (te2) -- node[edgelbl,right] {n} (ten2);
  \node[draw=none, fill=none, font=\footnotesize, text=black] at (6.6,1.0) {after insert ten};
  \node[draw=none, fill=none, font=\scriptsize, text=acc] at ([yshift=-5mm]ten2.south) {new};
\end{tikzpicture}
$$

### Search versus prefix test: the word-inside-a-word case

The distinction between $\textsc{Search}$ and `startsWith` comes down to the $isEnd$
flag, and the word set $\{\texttt{in}, \texttt{inn}\}$ exercises every case:

- `search("te")` walks `t`, `e` successfully but reads $isEnd = \text{false}$ at
  the `te` node: **false**. The path exists only as scaffolding for longer words.
- `startsWith("te")` walks the same two edges and returns **true** immediately —
  the node's existence is the witness.
- `search("in")` returns **true** even though `in` has a child: a terminal node
  may still be interior.
- `search("int")` fails at the third character — the `in` node has no `t` edge —
  and this is the _only_ way search fails: a missing edge, or a false flag at the
  end. There is no third failure mode.

Collected into one reference `Trie`, the interface is a direct transcription of
the $O(L)$ walks above: `insert` creates missing links as it descends,
`__contains__` and `starts_with` share a single `_node_at` walk that differ only
in whether they read $isEnd$, and `keys_with_prefix` runs the prefix-node walk
then DFSes the subtree. Hash-map children keep each node to the edges it actually
uses.

::impl{src="data-structures/trie.py"}

## Deleting a key: prune on the way back

Deletion requires care because of the shared structure. Clearing $isEnd$ at the
word's node is always correct (searches for the deleted word now return false),
but it can leave behind a chain of flagless, childless nodes that no surviving
key uses. Removing `ten` from our running trie by flag alone leaves
the `n` node dangling under `te` forever.

To address this, use a recursive delete that **prunes on the way back up**. Recurse
to the end of the word, clear the flag, then, as the recursion unwinds, delete
any node that is now _both_ flagless and childless; stop pruning at the first
node that still serves a purpose.

```algorithm
caption: $\textsc{Delete}(x, w, i)$ — remove $w$; returns true iff $x$ should be pruned
if $i > L$ then
  $isEnd(x) \gets \text{false}$        // reached the word's node
else
  $c \gets w_i$
  if $child(x, c) = \text{nil}$ then return false   // $w$ was never stored
  if $\textsc{Delete}(child(x, c), w, i+1)$ then
    $child(x, c) \gets \text{nil}$      // unlink the pruned child
return $isEnd(x) = \text{false}$ and $x$ has no children and $x \neq root(T)$
```

The return value is the pruning decision: a node survives if its flag is set
(it terminates another word) _or_ it still has a child (it lies on another
word's path). The word set $\{\texttt{in}, \texttt{inn}\}$ again covers the cases:

- **Delete `inn`.** Clear the flag on the deep `n` node; it has no children, so
  it is pruned and unlinked. Unwinding reaches the `in` node, whose flag is still
  true — pruning stops. One node removed.
- **Delete `in`** (from the original set). Clear the flag on the `in` node; it
  still has the `n` child leading to `inn`, so nothing is pruned. Zero nodes
  removed — the structure is untouched, only the flag flips.
- **Delete `tea`** from $\{\texttt{tea}\}$ alone: all three nodes fail the
  survival test in turn and the whole chain unwinds away.

Each case costs one $O(L)$ descent and one $O(L)$ unwind, so **delete is $O(L)$**
like everything else. An equivalent bookkeeping scheme stores a _reference count_
in each node — the number of stored words whose path passes through it —
incremented on insert, decremented on delete; a node is pruned when its count
hits zero. Same effect, and it also answers "how many words start with $p$?" in
$O(|p|)$.

$$
% caption: Prune-on-the-way-back in \{in, inn\}. Left: deleting \texttt{inn} clears its
%          flag, finds the node childless, and prunes it (dashed); the unwind stops at
%          \texttt{in}, still flagged. Right: deleting \texttt{in} only clears the flag —
%          the node stays, because \texttt{inn} still needs the path through it
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6mm, inner sep=0, font=\small},
  acc/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=6mm, inner sep=0, font=\small},
  gone/.style={circle, draw=black, dashed, minimum size=6mm, inner sep=0, font=\small},
  edgelbl/.style={draw=none, fill=none, font=\footnotesize},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % ---- left: delete inn ----
  \node (r1) at (0,0) {};
  \node (i1)  [below=11mm of r1] {};
  \node (in1) [below=11mm of i1, acc] {};
  \node (inn1)[below=11mm of in1, gone] {};
  \draw[->] (r1) -- node[edgelbl,left] {i} (i1);
  \draw[->] (i1) -- node[edgelbl,left] {n} (in1);
  \draw[black, dashed, ->] (in1) -- node[edgelbl,left] {n} (inn1);
  \node[draw=none, fill=none, font=\footnotesize, text=black] at (0,1.0) {delete inn};
  \node[draw=none, fill=none, font=\scriptsize, text=black] at ([xshift=13mm]inn1.east) {pruned};
  \node[draw=none, fill=none, font=\scriptsize, text=acc] at ([xshift=16mm]in1.east) {stop: still a word};
  % ---- right: delete in ----
  \node (r2) at (6.6,0) {};
  \node (i2)  [below=11mm of r2] {};
  \node (in2) [below=11mm of i2] {};
  \node (inn2)[below=11mm of in2, acc] {};
  \draw[->] (r2) -- node[edgelbl,left] {i} (i2);
  \draw[->] (i2) -- node[edgelbl,left] {n} (in2);
  \draw[->] (in2) -- node[edgelbl,left] {n} (inn2);
  \node[draw=none, fill=none, font=\footnotesize, text=black] at (6.6,1.0) {delete in};
  \node[draw=none, fill=none, font=\scriptsize, text=black, align=left] at ([xshift=17mm]in2.east) {f\/lag cleared, not pruned:\\inn needs it};
\end{tikzpicture}
$$

## Space and trade-offs

With array children the worst case is $O(n \cdot L \cdot |\Sigma|)$ pointers:
$n$ keys, up to $L$ nodes each, $|\Sigma|$ slots per node. That bound is
pessimistic, and tries are far better than it suggests _precisely when prefixes
are shared_: every common prefix collapses to a single path, so a dictionary of
English words (densely overlapping) stores far fewer than $n\cdot L$ nodes.
Hash-map children replace the $|\Sigma|$ factor with the actual child count,
trading a constant for the array's $O(1)$ indexing.

For example, with 64-bit pointers and
$|\Sigma| = 26$, an array node carries $26 \times 8 = 208$ bytes of child slots
plus the flag — call it 216 bytes — _whether it has 26 children or one_. Deep in
a trie most nodes have exactly one child (long unshared word tails), so almost
all of those slots hold nil. A 100{,}000-word dictionary that compresses to
roughly 250{,}000 nodes then occupies about $250{,}000 \times 216 \approx 54$ MB
of node storage, some fifty times the ~1 MB of raw text it encodes. Hash-map
children shrink a one-child node to one map entry, but each entry drags its own
overhead (hashing, buckets, per-entry headers — tens of bytes), and child lookup
gains a constant factor over a direct index. The binary trie sits at the other
extreme and is why the XOR trick below is cheap: $|\Sigma| = 2$ means just two
pointers, 16 bytes per node.

The regimes, then: **array children** when the alphabet is small and speed
matters (26 lowercase letters, 2 bits); **hash-map children** when the alphabet
is large or sparse (Unicode); a **radix tree** (end of this lesson) when memory
dominates and the one-child chains must go.

> **Remark (When to reach for a trie).** Over a hash set, a trie gives **ordered
> traversal** (an in-order DFS emits the keys sorted lexicographically), direct
> **prefix queries**, and **no hashing / no collisions**; its bound is a true
> worst case, not an expected one. Over a balanced BST it drops the $\log n$
> comparison factor and answers `startsWith` for free. The price is space when
> the alphabet is large and prefixes are _not_ shared — and cache behavior: a
> trie lookup chases $L$ pointers ($L$ potential cache misses), where a hash set
> hashes once and probes one bucket. For pure membership tests on random keys,
> the hash set usually wins in practice; the trie is the better choice when the
> _prefix structure_ of the keys is part of the question.

## Applications

**Autocomplete and prefix search.** To offer completions for what a user has
typed, walk to the node for the typed prefix in $O(L)$, then DFS the subtree
beneath it to enumerate every stored key with that prefix, since the trie has already
grouped them. The enumeration costs $O(L + s)$ where $s$ is the size of the
emitted subtree — proportional to the answer, not to the dictionary — and if the
DFS visits children in alphabet order, the completions come out already sorted.

::impl{algo="autocomplete"}

$$
% caption: Autocomplete for prefix \texttt{te}: walk to the prefix node in $O(L)$ (accent
%          path $t\to e$), then DFS the subtree to emit every completion — \texttt{tea},
%          \texttt{ted}, \texttt{ten} — already grouped under that node
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6mm, inner sep=0, font=\small},
  acc/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=6mm, inner sep=0, font=\small},
  edgelbl/.style={draw=none, font=\footnotesize, fill=none},
  accedge/.style={draw=acc, thick, ->},
  level distance=11mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (root) {};
  \node (t)  [below=11mm of root] {};
  \node (te) [below=11mm of t] {};
  \node (tea)[below left=11mm and 9mm of te, acc] {};
  \node (ted)[below=11mm of te, acc] {};
  \node (ten)[below right=11mm and 9mm of te, acc] {};
  \draw[accedge] (root) -- node[edgelbl,left] {t} (t);
  \draw[accedge] (t) -- node[edgelbl,left] {e} (te);
  \draw[->] (te) -- node[edgelbl,left] {a} (tea);
  \draw[->] (te) -- node[edgelbl,left] {d} (ted);
  \draw[->] (te) -- node[edgelbl,right] {n} (ten);
  \node[draw=none, font=\scriptsize, text=acc] at ([yshift=-5mm]tea.south) {tea};
  \node[draw=none, font=\scriptsize, text=acc] at ([yshift=-5mm]ted.south) {ted};
  \node[draw=none, font=\scriptsize, text=acc] at ([yshift=-5mm]ten.south) {ten};
  \node[draw=none, font=\footnotesize, text=acc] at ([xshift=20mm]te.east) {pref\/ix node};
  \node[draw=none, font=\footnotesize] at ([xshift=14mm]root.east) {walk $O(L)$};
\end{tikzpicture}
$$

**Wildcard dictionary (the "." problem).** _Design Add and Search Words_ asks for a
dictionary where a query may contain `.` matching any single character. Plain
search no longer follows one path: at a `.` we must branch into _all_ children
and recurse. Concrete characters keep the search $O(L)$; each `.` multiplies the
branching, but the trie still prunes any path that cannot match.

```algorithm
caption: $\textsc{WildSearch}(x, w, i)$ — match $w$ from node $x$, $w_i$ may be $\texttt{.}$
if $i > L$ then
  return $isEnd(x)$
if $w_i = \texttt{"."}$ then
  for each child $c$ of $x$ do
    if $\textsc{WildSearch}(c, w, i+1)$ then return true
  return false
else
  if $child(x, w_i) = \text{nil}$ then return false
  return $\textsc{WildSearch}(child(x, w_i), w, i+1)$
```

$$
% caption: Wildcard search for \texttt{t.n}: the concrete \texttt{t} follows one edge, the
%          \texttt{.} branches into every child (red, both \texttt{o} and \texttt{e}), and
%          only the \texttt{e} branch survives to spell \texttt{ten}. A \texttt{.} fans
%          the search; concrete characters keep it on one path
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6mm, inner sep=0, font=\small},
  acc/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=6mm, inner sep=0, font=\small},
  edgelbl/.style={draw=none, font=\footnotesize, fill=none},
  accedge/.style={draw=acc, thick, ->},
  redge/.style={draw=red!75!black, thick, ->},
  level distance=11mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (root) {};
  \node (t)  [below=11mm of root] {};
  \node (to) [below left=11mm and 14mm of t] {};
  \node (te) [below right=11mm and 8mm of t] {};
  \node (ten)[below=11mm of te, acc] {};
  \draw[accedge] (root) -- node[edgelbl,left] {t} (t);
  \draw[redge] (t) -- node[edgelbl,left] {o} (to);
  \draw[redge] (t) -- node[edgelbl,right] {e} (te);
  \draw[accedge] (te) -- node[edgelbl,right] {n} (ten);
  \node[draw=none, font=\scriptsize, red!75!black] at ([yshift=-4.5mm]to.south) {dead end};
  \node[draw=none, font=\scriptsize, text=acc] at ([yshift=-5mm]ten.south) {ten};
  \node[draw=none, font=\footnotesize, red!75!black, align=center] at ([xshift=22mm]t.east)
    {\texttt{.} tries\\all children};
\end{tikzpicture}
$$

In the worst case a query of $d$ dots over alphabet $\Sigma$ can visit
$|\Sigma|^d$ paths, so the bound degrades to $O(|\Sigma|^d \cdot L)$ — but every
branch dies the instant its next concrete character has no edge, and in a real
dictionary almost all of them die immediately. The figure's query `t.n` fans to
two children at the dot and kills the `o` branch one character later.

**Word search on a board.** _Word Search II_ hunts for many dictionary words in a
grid simultaneously. Building a trie of all target words lets one DFS over the
board carry a trie pointer alongside the grid position: the instant the current
board path spells a string that is _not a prefix of any target_, the missing trie
edge prunes the entire branch. One traversal finds all words, and the shared
prefixes mean overlapping targets share work.

::impl{algo="wildcard_dictionary,board_word_search"}

### The binary trie: maximum XOR pair

A non-string application treats a fixed-width integer as a string of bits over
$\Sigma = \{0, 1\}$. _Maximum XOR of Two Numbers_ asks for
$\max_{i,j} (a_i \oplus a_j)$. Brute force is $\Theta(n^2)$; a binary trie solves
it in $O(n \cdot b)$ for $b$-bit numbers.

Insert every number bit-by-bit from the **high bit down**, so each root-to-leaf
path of length $b$ is one number. To maximize the XOR of a query $a$ against the
stored set, walk down from the root and at each bit _greedily steer toward the
opposite bit_ of $a$: a differing bit contributes a $1$ at that (high) position.
If the opposite child exists, take it; otherwise follow the only child available.
The path traced spells the stored number that maximizes $a \oplus (\cdot)$.

The greedy choice is safe because of the geometric-series gap: winning bit
position $k$ is worth $2^k$, while _every_ lower position combined is worth at
most
$$
2^{k-1} + 2^{k-2} + \cdots + 2^0 \;=\; 2^k - 1 \;<\; 2^k.
$$
So any candidate that differs from $a$ at bit $k$ beats every candidate that
agrees there, no matter how the lower bits fall — the usual exchange argument
collapses to one inequality. The greedy walk never needs to backtrack, and one
subtlety makes it total: the trie stores complete $b$-bit paths (leading zeros
included), so whenever the preferred child is missing, the other child _must_
exist, and the walk always reaches depth $b$. Building the trie costs
$O(n \cdot b)$; querying each of the $n$ numbers costs $O(b)$; total
$O(n \cdot b)$ versus $\Theta(n^2 b)$ for brute force. For 32-bit values and
$n = 10^5$ that is $3.2 \times 10^6$ steps instead of on the order of $10^{10}$.

$$
% caption: Binary trie on \{010, 011, 110\}; greedy walk for a query maximizes XOR by
%          taking opposite bits
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6mm, inner sep=0, font=\small},
  term/.style={circle, draw, very thick, minimum size=6mm, inner sep=0, font=\small},
  acc/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=6mm, inner sep=0, font=\small},
  edgelbl/.style={draw=none, font=\footnotesize, fill=none},
  accedge/.style={draw=acc, thick, ->},
  level distance=11mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (r)   {};
  \node (z)   [below left=11mm and 16mm of r] {};
  \node (o)   [below right=11mm and 16mm of r] {};
  \node (z1)  [below=11mm of z] {};
  \node (o1)  [below=11mm of o] {};
  \node[term] (z10) [below left=11mm and 6mm of z1] {};
  \node[acc]  (z11) [below right=11mm and 6mm of z1] {};
  \node[term] (o10) [below=11mm of o1] {};
  \draw[accedge] (r) -- node[edgelbl,left] {0} (z);
  \draw[->] (r) -- node[edgelbl,right] {1} (o);
  \draw[accedge] (z) -- node[edgelbl,left] {1} (z1);
  \draw[->] (o) -- node[edgelbl,right] {1} (o1);
  \draw[->] (z1) -- node[edgelbl,left] {0} (z10);
  \draw[accedge] (z1) -- node[edgelbl,right] {1} (z11);
  \draw[->] (o1) -- node[edgelbl,right] {0} (o10);
  \node[draw=none, font=\scriptsize] at ([yshift=-5mm]z10.south) {$010$};
  \node[draw=none, font=\scriptsize, text=acc] at ([yshift=-5mm]z11.south) {$011$};
  \node[draw=none, font=\scriptsize] at ([yshift=-5mm]o10.south) {$110$};
\end{tikzpicture}
$$

The trie holds $\{010, 011, 110\}$. For the query $a = 100$ the greedy walk wants
the opposite bit at each level: $0, 1, 1$. The high bit of $a$ is $1$, so it takes
the $0$-child; the remaining two bits of $a$ are $0$, so at each step the wanted
opposite bit $1$ is available and the walk follows it. It lands on the stored
number $011$, giving $100 \oplus 011 = 111$, the maximum.

::impl{algo="maximum_xor_pair"}

### Multi-pattern and compressed variants

A trie of _patterns_ augmented with **failure links**, pointers that, on a
mismatch, jump to the longest proper suffix of the current match that is also a
prefix in the trie, is the [**Aho–Corasick**](/algorithms/sequences/suffix-arrays-and-aho-corasick) automaton: it scans a text once and
reports _every_ occurrence of _every_ pattern in linear time, the multi-string
generalization of [KMP](/algorithms/sequences/kmp-and-z-function) (which is single-pattern failure-link matching).[^erickson-ds]

For storage, a **compressed trie** (a _radix tree_ or **Patricia** trie) attacks
the one-child chains directly: contract every maximal chain of single-child,
unflagged nodes into one edge labeled by the whole substring.[^clrs-radix] Every
interior node then has at least two children (or is a terminal), which caps the
node count at $O(n)$ for $n$ keys — _independent of key length_ — because a tree
with $n$ leaves and no unary interior nodes has at most $n - 1$ interior nodes.
The stored strings shrink to one pointer-plus-length pair per edge.

In exchange, insertion is more intricate: a new key may match an edge label only
_partway_, forcing an **edge split**. Take a radix tree holding
$\{\texttt{tea}, \texttt{ten}\}$: one edge labeled `te` leaves the root, then
edges `a` and `n` branch to the two terminals. Inserting `to` walks the root
edge and mismatches at its second character ($\texttt{o} \neq \texttt{e}$), so
the edge splits at the common prefix `t`: a new interior node takes over, with
the remainder `e` of the old label on one side (keeping its `a`/`n` subtree
intact) and a fresh `o` edge on the other. One split per insert suffices, and
the operation stays $O(L)$.

$$
% caption: Radix-tree edge split. Left: \{tea, ten\} share the contracted edge \texttt{te}.
%          Right: inserting \texttt{to} matches only the \texttt{t}, so the edge splits at
%          a new interior node (dashed); the old \texttt{e} remainder keeps its subtree,
%          and \texttt{o} branches off fresh
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6mm, inner sep=0, font=\small},
  acc/.style={circle, draw=acc, very thick, fill=acc!15, minimum size=6mm, inner sep=0, font=\small},
  newnode/.style={circle, draw=acc, very thick, dashed, fill=acc!8, minimum size=6mm, inner sep=0, font=\small},
  edgelbl/.style={draw=none, fill=none, font=\footnotesize},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % ---- before ----
  \node (r1) at (0,0) {};
  \node (te1) [below=13mm of r1] {};
  \node (tea1)[below left=11mm and 8mm of te1, acc] {};
  \node (ten1)[below right=11mm and 8mm of te1, acc] {};
  \draw[->] (r1) -- node[edgelbl,left] {te} (te1);
  \draw[->] (te1) -- node[edgelbl,left] {a} (tea1);
  \draw[->] (te1) -- node[edgelbl,right] {n} (ten1);
  \node[draw=none, fill=none, font=\scriptsize, text=acc] at ([yshift=-5mm]tea1.south) {tea};
  \node[draw=none, fill=none, font=\scriptsize, text=acc] at ([yshift=-5mm]ten1.south) {ten};
  \node[draw=none, fill=none, font=\footnotesize, text=black] at (0,1.0) {before};
  % ---- after ----
  \node (r2) at (6.6,0) {};
  \node (t2) [below=13mm of r2, newnode] {};
  \node (te2) [below left=12mm and 10mm of t2] {};
  \node (to2) [below right=12mm and 10mm of t2, acc] {};
  \node (tea2)[below left=11mm and 6mm of te2, acc] {};
  \node (ten2)[below right=11mm and 6mm of te2, acc] {};
  \draw[->] (r2) -- node[edgelbl,left] {t} (t2);
  \draw[->] (t2) -- node[edgelbl,left] {e} (te2);
  \draw[->] (t2) -- node[edgelbl,right] {o} (to2);
  \draw[->] (te2) -- node[edgelbl,left] {a} (tea2);
  \draw[->] (te2) -- node[edgelbl,right] {n} (ten2);
  \node[draw=none, fill=none, font=\scriptsize, text=acc] at ([yshift=-5mm]tea2.south) {tea};
  \node[draw=none, fill=none, font=\scriptsize, text=acc] at ([yshift=-5mm]ten2.south) {ten};
  \node[draw=none, fill=none, font=\scriptsize, text=acc] at ([yshift=-5mm]to2.south) {to};
  \node[draw=none, fill=none, font=\footnotesize, text=black] at (6.6,1.0) {after insert to};
  \node[draw=none, fill=none, font=\scriptsize, text=acc] at ([xshift=13mm]t2.east) {split no\/de};
\end{tikzpicture}
$$

**Suffix trees** and **suffix arrays** push the compression idea further,
indexing _all suffixes_ of a text for fast substring search — the
[subject of the next lesson](/algorithms/sequences/suffix-arrays-and-aho-corasick).

## Where tries go in the real world

Tries are the standard structure for **IP routing**. A router must match a destination
address against a table of prefixes and forward on the _longest_ matching prefix
— exactly a prefix search in a binary trie over the address bits. Naive
bit-at-a-time tries are too slow for line-rate forwarding, so production routers
use compressed and multi-bit variants: the **Patricia trie** (Morrison,
_PATRICIA_, JACM 1968) collapses one-child chains just as this lesson's radix
tree does, and the **LC-trie** / multibit-trie families (Nilsson & Karlsson,
_IP-Address Lookup Using LC-Tries_, IEEE JSAC 1999) consume several bits per
node to bound the depth. The longest-prefix-match problem is the reason tries,
rather than hash tables, sit in the data plane of the internet.

The compression idea also scales to enormous static dictionaries through the
**DAWG** (directed acyclic word graph): merge not only shared prefixes, as a
trie does, but also shared _suffixes_, turning the trie into a minimal
deterministic automaton for the word set. This is the classic representation for
spell-checkers and Scrabble engines, storing hundreds of thousands of words in a
few hundred kilobytes. Pushed to indexing every substring of a text rather than a
fixed word list, the same automaton idea becomes the **suffix automaton**, a
cousin of the suffix arrays and Aho–Corasick automaton of the next lesson.

For storing a large set of strings where you only need membership tests and can
tolerate a small false-positive rate, tries compete with **succinct**
alternatives. A Bloom filter answers "have I seen this key?" in constant space
per element with no per-key pointers; a trie answers the same question exactly
and additionally supports prefix and ordered queries, at the cost of the
per-node pointer storage a Bloom filter avoids.

## Takeaways

- A **trie** is a rooted tree whose edges are labeled by characters; a
  root-to-node path spells a **prefix**, and an $isEnd$ flag marks nodes that
  complete a stored key — the flag is what distinguishes `in` stored as a word
  from `in` existing only as a prefix of `inn`. Children are an array of size
  $|\Sigma|$ or a per-node map.
- **Insert, search, delete, and `startsWith` all run in $O(L)$**, the key length,
  and are **independent of $n$**, beating a BST's $O(L\log n)$. Delete must
  **prune on the way back**: unlink nodes left flagless and childless, stopping
  at the first node another word still needs.
- Space is up to $O(n\cdot L\cdot|\Sigma|)$ with array children ($26 \times 8 =
  208$ bytes of slots per node, used or not), but **shared prefixes are stored
  once**, so prefix-heavy sets compress well; tries beat hash sets by giving
  **ordered traversal**, **prefix queries**, and **no collisions**, while hash
  sets win pure membership tests on cache behavior.
- Tries power **autocomplete** ($O(L+s)$, proportional to the output), **wildcard
  `.` matching**, and **board word-search pruning**; over $\{0,1\}$ a **binary
  trie** solves **maximum-XOR pair** in $O(n \cdot b)$ by greedily walking toward
  the opposite bit — safe because $2^k > 2^k - 1$, the worth of all lower bits
  combined.
- **Aho–Corasick** = trie + failure links = multi-pattern KMP; **Patricia / radix
  trees** contract single-child chains into substring-labeled edges, splitting an
  edge when an insert matches its label only partway, which caps the node count
  at $O(n)$; **suffix trees / arrays** index all suffixes of a text.

[^skiena-trie]: **Skiena**, § — String Data Structures: tries route keys character-by-character, giving $O(L)$ search independent of the number of stored strings.
[^erickson-ds]: **Erickson**, Ch. — Data Structures: tries as a string dictionary; failure links extend a trie into the Aho–Corasick multi-pattern matcher.
[^clrs-radix]: **CLRS**, Problem 12-2 — Radix trees: the trie over bit strings, sorted output by preorder traversal, and the compressed form.