When should you NOT use Trie (Prefix Tree)?

Avoid tries for pure exact-match lookups — a hash table has lower overhead and simpler implementation. Do not use a naive trie for Unicode strings without normalising to a fixed-width encoding — variable-width characters make per-character edge logic error-prone.

When is Trie (Prefix Tree) the right choice?

Use a trie for autocomplete or typeahead — retrieving all keys with a given prefix is a single traversal to the prefix node. Use it for IP routing table lookups (longest prefix match) where binary search on sorted CIDRs is too slow. Use a compressed trie (radix tree) when memory is a concern but prefix search semantics are still needed.

← Back to glossary

Trie (Prefix Tree)

data_structures Intermediate

TL;DR

A tree where each node represents a character — paths from root to leaf spell out keys, enabling O(m) lookup, prefix search, and autocomplete where m is key length, independent of dataset size.

Explanation

A trie stores strings by decomposing them character by character. Each edge represents one character; a path from the root to a marked node spells a complete key. Lookup, insert, and prefix search all run in O(m) time where m is the string length — completely independent of how many keys are stored. This makes tries superior to hash tables for prefix queries (autocomplete, IP routing, spell checking) where a hash table would require scanning all keys. A standard trie uses O(n×alphabet_size) memory which is often wasteful; compressed tries (Patricia/radix trees) merge single-child nodes to reduce memory. PHP's built-in data structures do not include a trie, but one can be implemented with nested arrays or SplFixedArray for the character map. Redis Sorted Sets and full-text search engines use trie variants internally for prefix lookups.

Watch Out

⚠ A trie without a dedicated end-of-word marker will incorrectly report that every prefix of an inserted key is also a stored key — always mark terminal nodes explicitly.

Common Misconception

✗ Tries are not always faster than hash tables — for exact-match lookups a hash table's O(1) average beats a trie's O(m). Tries win only when prefix queries or sorted key iteration are required.

Why It Matters

Autocomplete, IP routing tables, and spell checkers rely on prefix queries that hash tables and binary trees cannot serve efficiently at scale — a trie answers "all words starting with ph" in O(prefix_length) time.

Common Mistakes

Using a trie for exact-match-only lookups where a hash map is simpler and faster on average.
Naively implementing a trie with 26-slot arrays at every node — sparse character sets waste memory; use a map/dictionary per node instead.
Forgetting to mark end-of-word nodes — without an is_end flag, 'car' and 'card' both appear as stored keys when only 'card' was inserted.

Avoid When

Avoid tries for pure exact-match lookups — a hash table has lower overhead and simpler implementation.
Do not use a naive trie for Unicode strings without normalising to a fixed-width encoding — variable-width characters make per-character edge logic error-prone.

When To Use

Use a trie for autocomplete or typeahead — retrieving all keys with a given prefix is a single traversal to the prefix node.
Use it for IP routing table lookups (longest prefix match) where binary search on sorted CIDRs is too slow.
Use a compressed trie (radix tree) when memory is a concern but prefix search semantics are still needed.

Code Examples

💡 NoteThe bad example scans all 100k words on every keystroke — O(n) per character typed. The trie insert is O(word_length) once; prefix search traverses only the prefix path then collects matching subtree keys.

✗ Vulnerable

// Linear scan for prefix search — O(n) per query:
function autocomplete(array $words, string $prefix): array {
    return array_filter($words, fn($w) => str_starts_with($w, $prefix));
    // 100k words × every keystroke = very slow
}

✓ Fixed

// Trie insert + prefix search — O(prefix_len) to find node, O(results) to collect:
function trieInsert(array &$root, string $word): void {
    $node = &$root;
    foreach (str_split($word) as $ch) {
        $node = &$node[$ch];
    }
    $node['*'] = true; // end-of-word marker
}

function trieSearch(array $root, string $prefix): array {
    $node = $root;
    foreach (str_split($prefix) as $ch) {
        if (!isset($node[$ch])) return [];
        $node = $node[$ch];
    }
    return collectWords($node, $prefix);
}

References

↗ https://en.wikipedia.org/wiki/Trie