A hash set answers "is this exact string present" in O(1). A trie answers a genuinely different question — "which strings share this prefix" — by literally structuring the tree around shared prefixes, one character per level.
4 min read
words = {"cat", "car", "card", "care", "dog"}
"car" in words # O(1) — a hash set answers this fine
# But: "give me every word starting with 'ca'" — a hash set has no way to
# do this without checking every single stored word individuallyA hash set (from the hash-maps lesson) is excellent at "does this exact string exist," but it has no structural relationship between similar strings — "car" and "card" are hashed to completely unrelated positions, so finding "every word starting with ca" means scanning every stored word one by one, checking each against the prefix. A trie (pronounced "try," from retrieval) is a tree built specifically to make prefix questions fast, by literally organizing shared prefixes together as shared paths through the tree.
Each edge in a trie represents one character; walking from the root down some path spells out a string, character by character. Words sharing a prefix ("car", "card", "care") share the exact same path down to where they diverge — c, a, r is one shared path all three walk through, only splitting apart at the fourth character. This shared-path structure is the entire mechanism: prefix questions become "walk this many characters down the tree," rather than comparing full strings against each other.
class TrieNode:
def __init__(self):
self.children = {} # character -> TrieNode
self.is_end_of_word = False # True if a real word ends exactly here
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = TrueEach TrieNode holds a dict mapping "next character" to "the node reached by following it" — this is what lets insert("car") and insert("card") naturally share the same c -> a -> r chain of nodes, only branching where the words actually differ. is_end_of_word matters because a prefix existing in the trie (the path c -> a -> r exists because "card" was inserted) doesn't necessarily mean "car" itself was ever inserted as a real word — that flag is what distinguishes "this is a valid stopping point that's an actual word" from "this is just a node other words pass through."
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False # the path doesn't exist at all
node = node.children[char]
return node.is_end_of_word # path exists — but is it a real word, or just a prefix?
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True # path exists — that's all a prefix check needssearch and starts_with are almost the same walk, differing only in the final check — search requires the ending node to be a real word (is_end_of_word), while starts_with only cares that the path exists at all, since a prefix doesn't need to be a complete word itself. Both run in O(L) time, where L is the length of the word/prefix being checked — genuinely independent of how many words are stored in the trie at all, unlike scanning every stored word to check a prefix.
Hash set: O(1) exact lookup, but O(n) to find all words with a given prefix
Trie: O(L) exact lookup (L = word length), O(L + results) to find all words with a prefix
A trie doesn't win at everything — for pure "does this exact string exist" lookups, a hash set is typically simpler and at least as fast. What a trie buys specifically is efficient prefix operations: autocomplete (given "th", suggest "the", "this", "that"), spell-check dictionaries, and IP routing tables (matching the longest prefix of an address) all rely on exactly this "find everything sharing a prefix" capability that a plain hash set structurally cannot provide efficiently.
"Autocomplete," "find all words starting with X," "longest common prefix," or "does any word in this dictionary start with this sequence" are the tell — any problem phrased around prefixes specifically, rather than just exact membership. If the actual question is only ever "does this exact string exist," a plain hash set (from the hash-maps lesson) is simpler and does the job without the extra structure a trie requires.
Check your understanding
A quick comprehension check — not tracked, not graded, just for you.
1. Why can't a hash set efficiently answer 'find every word starting with ca'?
2. Why do 'car', 'card', and 'care' share the same nodes through part of a trie?
3. Why does a TrieNode need a separate is_end_of_word flag instead of just checking whether a path exists?
4. What's the actual difference between a trie's search() and starts_with() methods?
Data structures & algorithms