Chapter 102

Home

Trie Data Structure

A trie is a tree where each node represents a character, and paths from root to leaves spell words. O(L) insert/search for strings of length L — independent of how many strings are stored.

Trie for Prefix Queries

C++ — trie

struct TrieNode {
    TrieNode* children[26];
    bool is_end;
    TrieNode() : is_end(false) {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }
};

struct Trie {
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(string& s) {
        TrieNode* cur = root;
        for (char c : s) {
            int idx = c - 'a';
            if (!cur->children[idx]) cur->children[idx] = new TrieNode();
            cur = cur->children[idx];
        }
        cur->is_end = true;
    }

    bool search(string& s) {
        TrieNode* cur = root;
        for (char c : s) {
            int idx = c - 'a';
            if (!cur->children[idx]) return false;
            cur = cur->children[idx];
        }
        return cur->is_end;
    }
};

// O(L) per operation. Memory: O(total characters × alphabet size).

📐 Use trie for:

Prefix matching, autocomplete, spell checking, storing a dictionary (used in Aho-Corasick). For exact string matching, hash sets are simpler and faster.

Key Takeaways