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

debt(d7/e5/b5/t5)

d7 Detectability Operational debt — how invisible misuse is to your safety net

Closest to 'only careful code review or runtime testing' (d7). No detection_hints tools are listed. Misuse of a trie — such as using it for exact-match-only lookups, or forgetting end-of-word markers — will not be caught by a compiler or standard linter. These issues only surface during code review or when performance/correctness problems emerge at runtime. No SAST or specialist tool is cited that would catch trie misuse.

e5 Effort Remediation debt — work required to fix once spotted

Closest to 'touches multiple files / significant refactor in one component' (e5). quick_fix is not specified. Replacing a trie with a hash map for exact-match use cases, or fixing a naive 26-slot array node implementation to use a map per node, requires restructuring the trie node definition and likely updating traversal logic throughout the data structure implementation — more than a one-line patch but typically contained within one component.

b5 Burden Structural debt — long-term weight of choosing wrong

Closest to 'persistent productivity tax' (b5). applies_to is not specified, but tags include autocomplete, IP routing, and spell checkers — areas where the choice to use a trie shapes surrounding query and insertion logic. A trie imposes an ongoing structural commitment: every future maintainer must understand the node structure, traversal semantics, and prefix vs. exact-match trade-offs. Memory layout and character-set handling decisions (map vs. array nodes) affect performance across the component.

t5 Trap Cognitive debt — how counter-intuitive correct behaviour is

Closest to 'notable trap (a documented gotcha most devs eventually learn)' (t5). The misconception field states directly: 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). Many developers assume tries are universally faster for string operations. Additionally, the common_mistakes cite forgetting end-of-word markers as a correctness trap and naive 26-slot arrays as a memory trap. These are documented, learnable gotchas rather than catastrophic or deeply contradictory surprises.

About DEBT scoring → scored by claude-sonnet-4-6 · 2026-05-11 · reviewed by human

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