← All patterns

Trie

Prefix tree for word lookups, autocomplete, prefix counting, and word-search-in-grid. Each node has up to |Σ| children; operations are O(L) in the word length.

15 problems 3 Easy 8 Medium 4 Hard

Prefix tree storing strings as paths from the root. Each node has up to |Σ| children. O(L) insert/lookup per word, where L is the word length. Supports prefix queries (autocomplete), longest-common-prefix in O(L), and pruning for word-search-in-grid problems where many candidate words share prefixes.

For sparse alphabets, swap fixed arrays for hash-map children.

When to reach for this pattern

  • Lookup with prefix semantics (autocomplete, predictive)
  • Many word queries against a fixed dictionary
  • Longest / shortest unique prefix
  • Word-search-in-grid where prefix pruning helps

Canonical template 

struct Trie {
    Trie* ch[26] = {};
    bool end = false;
    void insert(const string& s) {
        Trie* t = this;
        for (char c : s) {
            if (!t->ch[c - 'a']) t->ch[c - 'a'] = new Trie();
            t = t->ch[c - 'a'];
        }
        t->end = true;
    }
    bool search(const string& s) {
        Trie* t = this;
        for (char c : s) {
            t = t->ch[c - 'a'];
            if (!t) return false;
        }
        return t->end;
    }
};

C++ · adapt the names and types to your problem.

Common pitfalls

  • Memory: 26 × n × L can balloon — use hash-map children for sparse alphabets
  • Forgetting to mark end = true — search returns true on prefixes that aren't words
  • Word-search-in-grid: must dedup outputs since multiple paths can reach the same word
  • Not cleaning up nodes on deletion — leaks if the trie is long-lived

Related patterns

Hash Maps Backtracking Tree DFS

Problems (15)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.