Tries and Prefix Trees

How a trie stores strings by shared prefixes, its operations and costs, the memory trade-off of fixed child arrays, and applications from autocomplete to maximum-XOR queries.

What you will learn

How a trie stores strings by shared prefixes, its operations and costs, the memory trade-off of fixed child arrays, and applications from autocomplete to maximum-XOR queries.

Prerequisites: Modules 6 and 11.

Concepts

Trie nodes, edges, end-of-word marker, insert, exact search, prefix search, deletion, lowercase alphabet versus map-based child storage, memory trade-offs.

Example

Explain that this compact node assumes lowercase English letters and requires input validation; Unicode/general alphabets need another representation.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Insert, search and prefix count are O(L) for a word of length L, independent of how many words are stored. Collecting all completions is depth-first, so they come out in lexicographic order. The 26-pointer node costs over 200 bytes even when it has one child; a hash map or sorted vector of children (or a compressed trie) trades speed for memory.

struct TrieNode {
    TrieNode* child[26]{};
    bool terminal = false;
};

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
    TrieNode* child[26]{};
    bool terminal = false;
    int pass = 0;                                   // words passing through: prefix counts
};
struct Trie {
    TrieNode root;
    static bool valid(const string& w) { return all_of(w.begin(), w.end(), [](char c) { return c >= 'a' && c <= 'z'; }); }
    void insert(const string& w) {
        if (!valid(w)) throw invalid_argument("only a-z supported: " + w);
        TrieNode* n = &root;
        for (char c : w) {
            int i = c - 'a';
            if (!n->child[i]) n->child[i] = new TrieNode();
            n = n->child[i];
            ++n->pass;
        }
        n->terminal = true;
    }
    const TrieNode* walk(const string& p) const {
        const TrieNode* n = &root;
        for (char c : p) { if (c < 'a' || c > 'z' || !(n = n->child[c - 'a'])) return nullptr; }
        return n;
    }
    bool contains(const string& w) const { auto n = walk(w); return n && n->terminal; }
    int countPrefix(const string& p) const { auto n = walk(p); return n ? n->pass : 0; }
    void collect(const TrieNode* n, string& cur, vector<string>& out) const {
        if (n->ter
…

contains car: true, contains ca: false
words with prefix "car": 4
autocomplete "car": car card care cart
node size: 216 bytes (26 pointers + flags)
rejected: only a-z supported: Café

Advanced topics

Compressed/radix tries, ternary search tries, bitwise tries for XOR queries, autocomplete ranking, prefix counting, dictionary matching, and memory optimization.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Choosing the opposite bit at the highest possible position is optimal because a 1 in bit b outweighs all lower bits combined. O(32) per query instead of O(n).

#include <bits/stdc++.h>
using namespace std;

// Maximum XOR of any two numbers: insert bits from high to low, greedily take the opposite bit
struct BitTrie {
    vector<array<int, 2>> next{{-1, -1}};
    void insert(unsigned x) {
        int n = 0;
        for (int b = 31; b >= 0; --b) {
            int bit = x >> b & 1;
            if (next[n][bit] == -1) { next[n][bit] = (int)next.size(); next.push_back({-1, -1}); }
            n = next[n][bit];
        }
    }
    unsigned bestXor(unsigned x) const {
        int n = 0; unsigned r = 0;
        for (int b = 31; b >= 0; --b) {
            int want = !(x >> b & 1);
            if (next[n][want] != -1) { r |= 1u << b; n = next[n][want]; } else n = next[n][!want];
        }
        return r;
    }
};

int main() {
    vector<unsigned> a = {3, 10, 5, 25, 2, 8};
    BitTrie t; unsigned best = 0;
    for (unsigned x : a) { t.insert(x); best = max(best, t.bestXor(x)); }
    unsigned brute = 0;
    for (unsigned x : a) for (unsigned y : a) brute = max(brute, x ^ y);
    cout << "max XOR = " << best << " (brute force " << brute << ")\n";
}

max XOR = 28 (brute force 28)

Practice

Easy: implement startsWith.

Medium: word search II — find all dictionary words in a letter grid (DFS over the grid, walking the trie).

Hard: add deletion that frees nodes no longer on any word's path.

Quiz

? Search for a word of length L in a trie holding n words costs…
+ O(L) :: One step per character, independent of n.
- O(log n) :: That is a balanced BST lookup (times comparison cost).
- O(n) :: No.
- O(n·L) :: That is a linear scan of the dictionary.

? `contains("ca")` returned false although "car" is stored. Why?
+ The node for "ca" exists but is not marked terminal. :: The end-of-word flag distinguishes words from prefixes.
- "ca" is not a valid word in English. :: The trie has no dictionary knowledge.
- Tries cannot store two-letter words. :: They can.
- A bug. :: Correct behaviour.

? When should you avoid the 26-pointer node? (select all that apply)
+ Large or Unicode alphabets :: Fixed arrays cannot represent them.
+ Memory-constrained sets of long, sparse words :: Most pointers stay null.
- Lowercase-only dictionaries where speed matters :: That is its best case.
+ When input is not validated :: An out-of-range index is undefined behaviour.