Suppose a word list must answer two questions: “Is this a word?” and “Which words start with this prefix?” A hash set handles the first well but not the second. A sorted list can answer both, while a trie takes another approach: it stores shared prefixes only once. That makes tries useful for word-game searches and typing completion. section 5.0 section 5.6
A trie is a tree whose edges carry characters. Follow edges from the root to spell a prefix; the node reached separates that prefix from its possible suffixes. Mark a node when its path spells a complete word. This distinction matters: a path can exist for “ca” without “ca” being a word. section 5.2
Figure 5.1 The trie for a nine-word list, laid out here left to right and in alphabetical order from top to bottom. Node numbers aren’t data in the tree; they’re included only so I can refer to them in the discussion that follows. Double-circle nodes represent ends of words.
The nine-word diagram makes prefix sharing visible: the paths for “car,” “care,” “cares,” and “cars” all pass through the same “car” node. section 5.2
To build a trie, start with an unmarked root. For each word, follow an existing edge for each character or create an edge and node when none exists. Mark the final node as an end of a word. Adding “care” after “car” reuses the c–a–r path and adds only the e edge. If edge lookup and insertion take O(1), processing n words of length m takes O(mn) time. section 5.2.2
Listing 5.3 A trie builder
sealed class TrieBuilder
{
private Node root = new(); #1
private TrieBuilder() { } #2
static public Node MakeTrie(IEnumerable<string> words)
{
var tb = new TrieBuilder();
foreach (var word in words)
tb.Add(word);
return tb.root;
}
private void Add(string word)
{
Node n = root;
foreach (char c in word)
n = n.TryAddNewNode(c);
n.IsEnd = true;
}
}
The C# builder shows the insertion invariant directly: advance once per character, then mark the node reached as a word ending. section 5.2.2
Lookup follows the queried characters from the root. A missing edge rules out both the word and any completion of that prefix; a full-word lookup also checks the end marker. To generate completions, find the prefix node and traverse its descendants, emitting each marked path—including the prefix itself if it is a word. A reusable StringBuilder avoids repeated string copying during traversal. Word lookup takes O(m) for a word of length m, compared with O(m log n) for the sorted-list approach. section 5.2.3 section 5.6
Sharing characters does not guarantee a smaller structure overall. In a nine-word example, 38 characters of input become just 13 character-labeled edges, but edges and nodes have overhead; nodes contain dictionaries. A larger word list can also produce many separate, logically identical leaf nodes. A trie shares prefixes, not suffixes. Merging equivalent suffix structures leads toward a directed acyclic word graph (DAWG), which connects this problem to finite-state automata. section 5.2.4 section 5.6
