Tries and prefix structures

A hash set answers "is card stored?" quickly. It can't answer "how many stored words start with ca?" or "what are the first five completions of ca, in order?" without looking at every word. A trie (prefix tree) can, in time proportional to the prefix, not the dictionary.

1. Words as paths

Each word is a path from the root, one edge per letter. Words that share a prefix share the nodes for it, and a flag marks where a word ends:

ca is a path but not a word — contains must check the end flag, not just that the path exists. That single distinction is the most common trie bug.

2. Representing nodes

How a node finds its children decides memory and speed:

The approach used throughout this skill: all nodes in one std::vector, children stored as indices (-1 = none). One allocation for many nodes, good locality, trivial cleanup — and, unlike references, indices stay valid when the vector grows.

#include <array>
#include <cstdint>
#include <print>
#include <string_view>
#include <vector>

struct Node {
    Node() { child.fill(-1); }
    std::array<std::int32_t, 26> child;
    std::size_t pass = 0;   // words whose path goes through this node
    bool end = false;
};

struct MiniTrie {
    std::vector<Node> nodes{Node{}};   // node 0 is the root

    void insert(std::string_view w) {
        std::int32_t cur = 0;
        ++nodes[0].pass;
        for (char ch : w) {
            int c = ch - 'a';
            if (nodes[cur].child[c] < 0) {
                nodes.push_back(Node{});   // may reallocate: hold indices, never Node&
                nodes[cur].child[c] = static_cast<std::int32_t>(nodes.size() - 1);
            }
            cur = nodes[cur].child[c];
            ++nodes[cur].pass;
        }
        nodes[cur].end = true;
    }

    std::int32_t walk(std::string_view s) const {
        std::int32_t cur = 0;
        for (char ch : s)
            if ((cur = nodes[cur].child[ch - 'a']) < 0) return -1;
        return cur;
    }
};

int main() {
    MiniTrie t;
    for (auto w : {"car", "cart", "cat", "dog"}) t.insert(w);
    std::int32_t ca = t.walk("ca");
    std::println("nodes: {}", t.nodes.size());
    std::println("'ca' is a word? {}", ca >= 0 && t.nodes[ca].end);
    std::println("words starting with 'ca': {}", t.nodes[ca].pass);
}

(This mini version skips duplicate checks and input validation — the build task needs both.)

3. Counting by prefix in O(prefix)

The pass field above is the trick for count_prefix: each node counts the stored words whose path goes through it. Walk the prefix and read the count — O(L) for a prefix of length L, no matter how many words sit below it. Walking the subtree and counting end flags instead is correct but costs O(words under the prefix); the build task's complexity probe catches exactly that.

The counts must stay exact:

• Duplicate insert: check contains first; a second insert of the same word must not bump anything.
• Erase: check the word is actually stored first. Erasing car when only cart exists must change nothing — otherwise the pass counts drift and every later prefix count is wrong.

4. Deletion and pruning

Erase decrements pass along the path. If some node's count reaches 0, no other word uses it — and since counts only shrink going down, nothing below it is used either. Unlink it from its parent and release it and its tail. If no count reaches 0 (the word is a prefix of other words), just clear its end flag:

Released indices go on a free list and are reused by later inserts, so a long insert/erase churn doesn't grow the node vector forever.

5. Ordered traversal: autocomplete

Visiting children in alphabetical order gives words in lexicographic order — provided you record a word when you enter its node, before its children (pre-order). Then app comes before apple, exactly like std::set iteration. Stop as soon as you have k words; with small k this is roughly O(L + k · word length), however big the dictionary.

void collect(int n, std::string& buf, std::size_t k, std::vector<std::string>& out) const {
    if (nodes[n].end) out.push_back(buf);           // pre-order
    for (int c = 0; c < 26 && out.size() < k; ++c) {
        if (int next = nodes[n].child[c]; next >= 0) {
            buf.push_back('a' + c);
            collect(next, buf, k, out);
            buf.pop_back();                        // backtrack
        }
    }
}

6. Wildcards — faded example

match("b.d") should find bad, bed, bid, bud: . matches exactly one letter. It's backtracking over the trie: a letter follows one child, a . tries every child, and when the pattern is used up you record the word if the node ends one. Fill in the two marked lines:

void match_from(int n, std::string_view rest, std::string& buf, std::vector<std::string>& out) const {
    if (rest.empty()) {
        if (/* ??? */) out.push_back(buf);
        return;
    }
    int lo = 0, hi = 25;
    if (rest[0] != '.') lo = hi = /* ??? */;
    for (int c = lo; c <= hi; ++c)
        if (int next = nodes[n].child[c]; next >= 0) {
            buf.push_back('a' + c);
            match_from(next, rest.substr(1), buf, out);
            buf.pop_back();
        }
}

7. Validate before you index

c - 'a' is only a valid index for 'a'…'z'. 'A' - 'a' is −32, and a byte above 127 in a char is negative too. Indexing child[-32] reads some other part of memory — and when nodes sit together in one vector, that memory belongs to a neighbouring node, so ASan sees nothing wrong. std::array with the hardened library (-D_GLIBCXX_ASSERTIONS, which the grader enables) does catch it — but the fix is to reject invalid input before using it as an index.

8. Variations

Compressed tries (radix trees) merge chains of single-child nodes into one edge labelled with a whole string: far fewer nodes for sparse dictionaries (routing tables, file paths), at the cost of splitting edges on insert.

Binary tries store integers bit by bit, most significant first. The classic use is maximum XOR pair: for each number, walk the trie preferring the opposite bit at every level.

#include <array>
#include <cstdint>
#include <print>
#include <vector>

int main() {
    std::vector<std::array<int, 2>> trie{{-1, -1}};
    auto insert = [&](std::uint32_t x) {
        int cur = 0;
        for (int b = 31; b >= 0; --b) {
            int bit = (x >> b) & 1;
            if (trie[cur][bit] < 0) {
                trie.push_back({-1, -1});
                trie[cur][bit] = static_cast<int>(trie.size() - 1);
            }
            cur = trie[cur][bit];
        }
    };
    auto best_xor = [&](std::uint32_t x) {
        int cur = 0;
        std::uint32_t result = 0;
        for (int b = 31; b >= 0; --b) {
            int want = ((x >> b) & 1) ^ 1;   // prefer the opposite bit
            if (trie[cur][want] >= 0) { result |= 1u << b; cur = trie[cur][want]; }
            else cur = trie[cur][want ^ 1];
        }
        return result;
    };
    std::vector<std::uint32_t> xs{3, 10, 5, 25, 2, 8};
    std::uint32_t best = 0;
    for (auto x : xs) {
        if (trie.size() > 1) best = std::max(best, best_xor(x));
        insert(x);
    }
    std::println("max xor pair: {}", best);   // 5 ^ 25 = 28
}

Aho–Corasick (preview) adds "failure links" to a trie of patterns so you can find every occurrence of every pattern in a text in one pass — O(text + patterns + matches). It's what grep -F with many patterns and intrusion-detection systems use.

Summary

• A trie stores words as paths; a word is a path plus an end flag.
• Keep nodes in one vector with index children and a free list.
• A per-node pass count makes count_prefix O(prefix length).
• Check before you change: no count updates for duplicates or for erasing non-words. Prune nodes whose count reaches 0.
• Pre-order DFS with children a..z gives lexicographic autocomplete.
• Validate characters before c - 'a'.