Home/Trees/Trie
Search algorithmsCTRL K

Trie

· one node per character, prefixes shared
/trees/trie
NODES
1
characters stored once
WORDS
0/ 8
inserted
CREATED
0
nodes added so far
OPERATION
insert
running now
MATCHES
—
words under the prefix
currentpath followedcreatedend of a word
8 words · seed 7 · 46 steps
step 0 / 45
Words8
trie.ts
1
class Trie {
2
  root = new TrieNode();
3
  insert(word: string) {
4
    let node = this.root;
5
    for (const char of word) {
6
      if (!node.children.has(char)) node.children.set(char, new TrieNode());
7
      node = node.children.get(char)!;
8
    }
9
    node.end = true;
10
  }
11
  search(word: string) {
12
    let node: TrieNode | undefined = this.root;
13
    for (const char of word) node = node?.children.get(char);
14
    return node !== undefined && node.end;
15
  }
16
  startsWith(prefix: string) {
17
    let node: TrieNode | undefined = this.root;
18
    for (const char of prefix) node = node?.children.get(char);
19
    return node ? node.collect(prefix) : []; // every end below, depth first
20
  }
21
}
CURRENT STEP
line 2

An empty trie: one root, no characters. 8 words will go in: cape, seat, arm, sea, car, sum, dot, cart.

// how it works

Understanding Trie

trie · the autocomplete data structure
01

The idea

A trie stores strings as paths. Every node holds one character and the words that share a prefix share the path of that prefix; a flag on a node says a word ends there. Inserting or looking up a word walks one node per character, so the cost is the length of the word, whatever the number of words stored.

Because a prefix is a node, everything under that node is the list of completions: startsWith walks the prefix and then collects the ends below it. That is why search boxes, spell checkers and IP routers keep their keys in tries, and why memory is the price: a node per character, with a map of children each.

02

The four stages

1
followthe child for the next character, if it exists
2
createa child when it does not
3
markthe last node as the end of a word
4
collectevery end below a prefix
03

Complexity

best
O(m)m the length of the word
average
O(m)independent of the number of words
worst
O(m + k)prefix query returning k words
space
O(n · m)a node per character in the worst case
04

Versus its siblings

LOOKUP COST · 1 000 000 WORDS OF LENGTH 8
trie
8
hash table
9
sorted array (binary search)
160
balanced bst
160
character comparisons · the tree searches compare whole strings at each of log n levels
05

Pseudocode

INSERT(word): node ← root; for each character: node ← its child for the character, created if missing; mark node as an end
SEARCH(word): node ← root; for each character: node ← its child, or fail; return whether node is an end
STARTSWITH(prefix): walk the prefix the same way, then collect every end below that node
06

When to use

Autocomplete, spell checking, T9 keyboards: anything that asks for all keys with a prefix.
Longest-prefix matching, the core of IP routing tables, and string sets with many shared prefixes.
07

Pitfalls

Memory: a node per character with a child map is heavy; radix trees merge single-child chains, and arrays of 26 waste space on sparse nodes.
Deletion must unmark the end and prune nodes that no longer lead anywhere.
For exact lookups only, a hash table is simpler and usually faster.
08

History

René de la Briandais described the structure in 1959 and Edward Fredkin named it in 1960, from retrieval, pronouncing it 'tree' to the confusion of everyone since. Radix trees and Patricia tries (Morrison, 1968) compress it, and it underlies most predictive text and routing tables today.

Back to Trees