Tries (Prefix Trees)
debt(d7/e5/b3/t5)
Closest to 'only careful code review or runtime testing' (d7). The detection_hints indicate no automated tooling exists for this concept — the code_pattern note says a LIKE 'term%' database query is a candidate for a trie, but spotting this misuse requires a developer familiar with data structures to review query patterns or notice performance degradation in production. No linter or SAST tool from the term's detection_hints can flag this.
Closest to 'touches multiple files / significant refactor in one component' (e5). The quick_fix describes implementing a trie with PHP arrays per node — replacing a database LIKE query or hash map with a trie (or vice versa) requires building the data structure, migrating the data population logic, and updating query/search call sites. This is more than a one-line patch but typically contained within one component or feature area.
Closest to 'localised tax' (b3). A trie implementation in PHP is a localised data structure choice — it applies to a specific autocomplete or prefix-search feature within web or CLI contexts, not broadly across the codebase. Future maintainers of that feature pay the tax (understanding trie structure, terminal node marking, memory considerations) but the rest of the codebase is largely unaffected.
Closest to 'notable trap (a documented gotcha most devs eventually learn)' (t5). The misconception field calls out that developers assume a hash map is always better for string lookup, missing that tries support prefix search which hash maps cannot do efficiently. Common mistakes reinforce additional gotchas: not marking terminal nodes (confusing prefixes with stored words), memory waste from naive 26-element arrays, and case-sensitivity issues. These are documented traps that developers reliably stumble into.
Also Known As
TL;DR
Explanation
A Trie (from re-TRIE-val) stores strings character by character — each node represents one character, and a path from root to a terminal node spells a complete word. Lookup and insert are O(m) where m is the string length, independent of the number of stored strings. Prefix search (all words starting with 'pre') is O(m + k) where k is the number of matches. Applications: autocomplete, spell checkers, IP routing tables, and dictionary implementations. Space can be improved with compressed tries (Patricia/Radix trees).
Common Misconception
Why It Matters
Common Mistakes
- Using a Trie when only exact lookups are needed — a hash map is simpler and faster.
- Not marking terminal nodes — the Trie cannot distinguish between 'car' as a stored word vs 'car' as a prefix of 'card'.
- Naive Trie with 26-element arrays per node — wastes memory; use a hash map per node for sparse alphabets.
- Forgetting that Trie lookup is case-sensitive by default — normalise input.
Code Examples
// Linear scan for prefix search — O(n * m):
$words = ['apple','application','apply','banana','band'];
$prefix = 'app';
$results = array_filter($words, fn($w) => str_starts_with($w, $prefix));
// O(n) scan for every prefix query — unusable at scale// Trie — O(m) prefix search regardless of dictionary size:
class TrieNode {
public array $children = [];
public bool $isEnd = false;
}
class Trie {
private TrieNode $root;
public function __construct() { $this->root = new TrieNode(); }
public function insert(string $word): void {
$node = $this->root;
foreach (str_split($word) as $char) {
$node->children[$char] ??= new TrieNode();
$node = $node->children[$char];
}
$node->isEnd = true;
}
// search(), startsWith(), getSuggestions() all O(m)
}