Trie (Prefix Tree)

Trees O(L) O(Σ · N)

A tree keyed by characters: each root-to-node path spells a prefix, so insert and lookup cost only the length of the word.

WordsSearch

1/25

Insert "cat": create node for 'c'.

InvariantThe path from the root spells a prefix; a node's descendants are exactly the words extending it.

currentcompareinsertremoverotate

trie.c

#define R 26
typedef struct Trie {
    struct Trie *next[R];
    int end;
} Trie;
 
void insert(Trie *root, const char *w) {
    Trie *node = root;
    for (int i = 0; w[i]; i++) {
        int c = w[i] - 'a';
        if (!node->next[c])
            node->next[c] = newTrie();
        node = node->next[c];
    }
    node->end = 1;
}
 
int search(Trie *root, const char *w) {
    Trie *node = root;
    for (int i = 0; w[i]; i++) {
        int c = w[i] - 'a';
        if (!node->next[c]) return 0;
        node = node->next[c];
    }
    return node->end;
}

How Trie (Prefix Tree) works

One tree node per character; a word is a root-to-node path. All words sharing a prefix share that path, so lookup cost depends on word length, not dictionary size.

When to use it

Autocomplete, prefix search, spell checkers, IP routing tables.