Trie (Prefix Tree)
A trie is a tree where each node represents one character of a string, and paths from root to marked nodes represent words in the dictionary.
Trie = a T-REE of letters, like a phone's autocomplete keyboard. Type 'c-a-t' and each letter narrows the branch. Shared prefixes ('car', 'cat') share the same hallway until they diverge.
Insert: O(m) where m is word length. Search: O(m). Prefix search: O(m) to reach the prefix node, then enumerate. Each node stores a map of children and an end-of-word flag. Space: O(ALPHABET_SIZE * m * n) in worst case (array-based children), or O(m * n) with hash map children. Use cases: autocomplete, spell checker, IP routing (radix tree), word search in grid.
Array-backed trie (children[26]) has O(1) child lookup but wastes space for sparse alphabets. Hash map-backed trie is memory-efficient but slower. Compressed trie (radix tree) merges single-child chains into edge labels — reduces space. Suffix trie stores all suffixes and supports substring search in O(m) — but O(n²) space. Suffix array + LCP achieves same in O(n) space (with O(n) or O(n log n) construction time). Aho-Corasick automaton adds failure links to a trie for O(n + m + z) multi-pattern search (n=text length, m=total pattern length, z=match count).
I build a trie when I need prefix-based operations that a hash map can't give efficiently — like 'find all words with prefix X' or 'check if any word in dictionary matches a pattern'. I implement it with a TrieNode class containing a children dict and is_end flag. Time per operation is O(word length), independent of dictionary size — much better than scanning all words. For the word search grid problem, I build a trie of the dictionary first, then DFS on the grid using the trie to prune dead-end paths.
Forgetting to mark is_end at the end of insert means search always returns false. Also: deleting from a trie requires careful cleanup — if you delete a word that shares a prefix with another word, you must NOT delete shared nodes. Set is_end=false for the deleted word's terminal node only.