Tries (prefix trees)
Store words letter by letter in a tree so that lookups and prefix searches cost O(length of the word), build autocomplete, and know when a trie beats a HashSet.
HashSet<string> can tell you instantly whether “bolt” exists, but it cannot answer “which words start with bo?” without checking every word. A trie (from retrieval, usually said “try”) answers prefix questions directly.
One letter per edge
A trie in C#
using System.Text; var trie = new Trie();foreach (var w in new[] { "beam", "bear", "bolt", "bolts", "brace", "column" }) trie.Insert(w); Console.WriteLine(trie.Contains("bolt"));Console.WriteLine(trie.Contains("bea")); // only a prefix, not a wordConsole.WriteLine(trie.StartsWith("bea"));Console.WriteLine(string.Join(", ", trie.WordsWithPrefix("b"))); class Trie{ private class Node { public Dictionary<char, Node> Children { get; } = new(); public bool IsWord; } private readonly Node _root = new(); public void Insert(string word) { var n = _root; foreach (char c in word) { if (!n.Children.TryGetValue(c, out var next)) n.Children[c] = next = new Node(); // create the missing step n = next; } n.IsWord = true; } private Node? Find(string prefix) { var n = _root; foreach (char c in prefix) { if (!n.Children.TryGetValue(c, out var next)) return null; // path breaks off n = next; } return n; } public bool Contains(string word) => Find(word)?.IsWord == true; public bool StartsWith(string prefix) => Find(prefix) is not null; public List<string> WordsWithPrefix(string prefix) { var result = new List<string>(); var start = Find(prefix); if (start is not null) Collect(start, new StringBuilder(prefix), result); return result; } private static void Collect(Node n, StringBuilder sb, List<string> result) { if (n.IsWord) result.Add(sb.ToString()); foreach (var (c, child) in n.Children.OrderBy(p => p.Key)) // alphabetical { sb.Append(c); Collect(child, sb, result); sb.Length--; // undo the letter } }}True False True beam, bear, bolt, bolts, brace
How fast is it?
| Question | HashSet<string> | Sorted array + binary search | Trie |
|---|---|---|---|
Where tries are used
Autocomplete and search suggestions, spell checkers (“did you mean…”). Routing tables: an internet router finds the longest matching prefix of an IP address, stored bit by bit in a binary trie. Word games and puzzles: stop searching a path the moment no word starts with the letters so far. Prefix codes: Huffman compression decodes bits by walking a binary trie.
CountingTrie where CountWithPrefix(string prefix) returns how many inserted words start with prefix, in O(length of the prefix), without walking the subtree. Words: beam, bear, bolt, bolts, brace. Expected: b → 5, bo → 2, bea → 2, c → 0. (Assume each word is inserted once.)
Show a hint
Show the solution
var t = new CountingTrie();foreach (var w in new[] { "beam", "bear", "bolt", "bolts", "brace" }) t.Insert(w);foreach (var p in new[] { "b", "bo", "bea", "c" }) Console.WriteLine($"{p}: {t.CountWithPrefix(p)}"); class CountingTrie{ private class Node { public Dictionary<char, Node> Children { get; } = new(); public int Count; // words that pass through this node } private readonly Node _root = new(); public void Insert(string word) { var n = _root; foreach (char c in word) { if (!n.Children.TryGetValue(c, out var next)) n.Children[c] = next = new Node(); next.Count++; n = next; } } public int CountWithPrefix(string prefix) { var n = _root; foreach (char c in prefix) { if (!n.Children.TryGetValue(c, out var next)) return 0; n = next; } return n.Count; }}b: 5 bo: 2 bea: 2 c: 0
Remember
A trie stores strings letter by letter; each node is a prefix, shared by all words that start with it. Insert, lookup and prefix checks are O(length of the word), independent of how many words are stored. Mark word ends explicitly: a word can end in the middle of a longer word’s path. Tries shine for prefix queries (autocomplete, routing) but use more memory than a HashSet.