Trie: The Prefix Tree, Step by Step

Sixteen words sit in a tree, one letter per node, and words that begin alike share their beginning: car, card and cart run down the same c, a, r. A double ring marks the node where a word ends. Type a word, choose an operation and step through it.

Worked example — Trie: The Prefix Tree, Step by Step

Trie, look up “car”: letters read	3, stored
Binary search, sorted list: letters compared	12 in 4 probes
Hash table, no collisions: letters read	6
Words starting with “car”	6: car, card, care, careful, cargo, cart
Sorted list: probes, then words read forward	12
Hash table: words read (all of them)	16
Inserting “car” adds	0 nodes: 0 bytes to the trie, 0 to the list
Sorted list: words moved to make room	0

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Trie: The Prefix Tree, Step by Step

A trie, or prefix tree, stores a set of words as a tree with one node for every distinct prefix of them. The root stands for the empty prefix, each edge carries one letter, so the path from the root to a node spells that node's prefix, and a node is marked when its prefix is a whole stored word. Words that begin alike share the path for their common beginning. A lookup follows the word's letters from the root; a prefix search walks to the prefix's node and lists every marked node below it. Edward Fredkin named the structure in 1960, from retrieval, and meant it to be said like tree.

What each symbol means

W: the number of words in the list
L: the number of letters in all of them together
N: the number of nodes, one per distinct prefix, the root not counted

Assumes: Lowercase a to z, one byte per letter, 64-bit pointers, and no padding or allocator overhead in either structure. Binary search counts every pair of letters it compares and stops at the first pair that differ; reaching the end of a word costs it nothing. The hash table is given no collisions at all, its best case. The 18-byte node keeps its children in alphabet order, so a search along them stops as soon as it passes the letter it wants.

Binary search reads c, a, r four times; the trie reads them once 🖖

Press Look up car. The trie follows one letter per step and finds car marked as a word: 3 letters. Binary search over the same sixteen words, sorted, probes catch, careful, card and car, and each of them begins with ca, so every comparison reads three letters before it can decide which way to go: 12 in all. A hash table reads the three letters to compute a slot and three more to check the word it finds there, 6. Over all sixteen stored words the trie reads 70 letters, the hash table 140 and binary search 169. The shared beginnings that save the trie its nodes are what make binary search's comparisons long. Store all 17,576 strings of three letters, aaa to zzz, and binary search needs 26.4 letters on average to find one; the trie still reads 3.

A sorted list can autocomplete too. A hash table has to read every word 🖖

Press Words starting with car. The trie walks c, a, r and then visits the 8 nodes below car, 11 nodes in all, and six of them end a word. Dog, plan and the rest are never touched. A sorted list gets the same property another way, because words that begin with car sort next to each other. Binary search finds the first of them in 5 probes, and reading forward collects all six and stops at cat, the first word that does not fit: 12 words read. A hash table is built to send car, card and cargo to unrelated slots, so it has to read all 16 words and test each one. Where the trie does beat the sorted list is in growing. Press Insert carpet: the trie adds 3 nodes and moves nothing, while the sorted list shifts its pointers to 11 words one place along to make room.

Sharing 40 of 70 letters still leaves the trie 2.6 times the size of the list 🖖

The sixteen words have 70 letters, and the trie holds them in 30 nodes because car, card, care and the rest store their c, a, r once. A node is not a letter, though. The lean layout gives each node a byte for its letter, a byte for the end mark and two 8-byte pointers, to its first child and to its next sibling: 18 bytes, and 31 nodes with the root come to 558. The plain list stores each letter in a byte, plus an end byte and an 8-byte pointer per word: 214. Give each node a pointer for every letter of the alphabet, so that each step is one array index, and the trie takes 6,479 bytes, 30 times the list. With words of at most 14 letters, as here, a new word costs the trie less only if it adds no node at all, as plan would to a trie already holding planet, or adds one node and has at least ten letters. The lean layout pays in time as well: it finds each letter by walking along the siblings, and doorbell then takes 10 comparisons, one more than binary search.

Problem solved in full

How much sharing would make the trie the smaller one? 4 steps
Press Long words: 85 letters in 21 nodes, three quarters of them shared, and the trie of 18-byte nodes still takes 396 bytes against the list's 157. Among lists whose words all have k letters, the trie does best against the list when the list holds every possible one. Under the page's byte counts, what is the shortest k for which that trie is smaller than the plain list?

Open this problem in the tool
1. On the page: 21 nodes and the root, 22 × 18 = 396 bytes. The list stores 85 letters and, for each of its 8 words, an end byte and an 8-byte pointer: 85 + 9 × 8 = 157.
  
  $22 \times 18 = 396, 85 + 9 \times 8 = 157$
2. Every string of k letters is 26^k words of k letters each, so the list takes (k + 9) × 26^k bytes.
  
  $list = (k + 9) \cdot 2 6^{k}$
3. The trie needs a node for every string of 1 to k letters: 26 + 26² + … + 26^k, a little under 26/25 × 26^k. Add the root, multiply by 18, and the trie takes just under 18.72 × 26^k bytes.
  
  $N = 26 + 2 6^{2} + \dots + 2 6^{k} = \frac{26}{25} (2 6^{k} - 1), 18 (N + 1) < 18.72 \cdot 2 6^{k}$
4. So the list is the larger one once k + 9 passes 18.72, which first happens at k = 10. At k = 9 the trie is 4.0% larger than the list; at k = 10 it is 1.5% smaller.
  
  $k + 9 > 18.72 ⟺ k \geq 10 : \frac{trie}{list} = 1.040 (k = 9), 0.985 (k = 10)$
Answer

Ten letters, with all 26¹⁰ of them in the list, about 1.4 × 10¹⁴ words. With 209-byte nodes the same sum asks for k + 9 to pass about 217, words of 209 letters.

$k = 10, 2 6^{10} \approx 1.4 \times 1 0^{14} words$

Learning path

What a data structure makes cheap

References (3)

The name, its origin in "retrieval", and Fredkin's intended pronunciation, quoted in the definition: Paul E. Black, "trie", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., NIST, entry modified 12 February 2019.
The paper that named the structure: Edward Fredkin, "Trie memory," Communications of the ACM 3(9), September 1960, pp. 490–499.
The earlier description of searching on letter-by-letter keys: René de la Briandais, "File searching using variable length keys," Papers presented at the Western Joint Computer Conference, San Francisco, 3–5 March 1959, pp. 295–298.

By the 42Math team · Reviewed against published sources. Corrections welcome.