Tries (Prefix Trees)

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)
}

References

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

Tags

Related Terms