-
Notifications
You must be signed in to change notification settings - Fork 0
010 — Tries
BSTs branch on "is this value bigger or smaller." Heaps branch on "is this more or less urgent." A trie branches on something completely different: one character at a time.
Think about how your phone's keyboard autocompletes as you type. You tap c, and it already knows the only words that matter now are the ones starting with c. You tap a, narrowing to words starting with ca. You tap t — now it's down to "cat," "catch," "cattle." Every keystroke doesn't restart the search from scratch; it just walks one step deeper into an already-known structure of "what comes next after what I've typed so far."
- 🔤 Every node in that structure represents "the set of all words that share this exact prefix."
- 🌳 Walking from the root to any node spells out a prefix, one character per edge.
- 🚩 Some nodes are flagged "a complete word ends here" — "cat" is both a complete word and a valid prefix of "catch."
That's a trie (pronounced "try," from retrieval): a tree purpose-built for prefixes.
A trie (also called a prefix tree) is a tree where:
- Each edge is labeled with a single character, not a value comparison.
- Each node represents the string formed by the path from the root down to it.
- Each node has a
childrencollection (commonly a dictionary keyed by character) instead of a fixed left/right pair — a trie node can branch into as many children as there are distinct next-characters. - Certain nodes are marked
isEndOfWord = true, meaning the path from the root to that node spells a complete, inserted word — not just a prefix of a longer one.
This is genuinely different from a BST: a BST branches based on a comparison (< or >) between whole values; a trie branches based on the identity of the next character, and the "value" at any node is really just its path from the root.
Swift has no stdlib trie — like the other structures in this chapter, it's hand-rolled: a TrieNode class holding a [Character: TrieNode] dictionary of children plus a boolean flag.
Reach for a trie when:
- You need fast prefix queries — autocomplete, spell-checkers, IP routing tables, "does any word in my dictionary start with this substring."
- You're checking membership across many strings that share common prefixes — a trie shares that shared storage instead of duplicating it, which a
Set<String>cannot do. - A problem explicitly mentions "prefix" — that word is the single strongest signal a trie is the intended structure.
Skip it when you just need "is this exact string in my collection" with no prefix requirement — a plain Set<String> gives you O(1)-average membership with far less code and memory overhead.
A trie after inserting "cat", "car", "care", and "dog":
(root)
/ \
c d
| |
a o
/ \ |
t r g ✅ ("dog")
✅ |
("cat") e ✅ ("care")
(also: "car" ends at r,
marked ✅ before descending to e)
Walking c → a → r spells the prefix "car" — that node is ✅ (a
complete word) AND has a child e, because "care" extends past it.
Walking c → a → t spells "cat" — ✅, and it's a leaf (no children).
Two things this diagram makes clear that a plain list of strings hides: "car" and "care" share the c → a → r path — no duplicated storage — and a node being isEndOfWord doesn't stop it from having children (a word can be a prefix of a longer word).
No stdlib equivalent — hand-rolled with a dictionary-backed children map.
final class TrieNode {
var children: [Character: TrieNode] = [:]
var isEndOfWord = false
}
final class Trie {
private let root = TrieNode()
func insert(_ word: String) {
var node = root
for char in word {
if let next = node.children[char] {
node = next
} else {
let next = TrieNode()
node.children[char] = next
node = next
}
}
node.isEndOfWord = true
}
func search(_ word: String) -> Bool {
guard let node = walk(word) else { return false }
return node.isEndOfWord
}
func startsWith(_ prefix: String) -> Bool {
walk(prefix) != nil
}
// Shared helper: walk the trie one character at a time, returning the
// node reached, or nil if the path breaks before the string is exhausted.
private func walk(_ text: String) -> TrieNode? {
var node = root
for char in text {
guard let next = node.children[char] else { return nil }
node = next
}
return node
}
}Usage:
let trie = Trie()
["cat", "car", "care", "dog"].forEach { trie.insert($0) }
trie.search("car") // true — inserted exactly, and marked end-of-word
trie.search("ca") // false — "ca" is a path in the trie, but never marked end-of-word
trie.startsWith("ca") // true — the path c → a exists, regardless of end-of-word
trie.startsWith("do") // true
trie.search("dog") // trueNote search("ca") returning false while startsWith("ca") returns true — that's the entire point of the isEndOfWord flag: it's what separates "this is a valid path" from "this path spells a word that was actually inserted."
Let L be the length of the word or prefix involved — this is the variable that matters for tries, not n (the number of stored words).
| Operation | Big-O | Why |
|---|---|---|
| Insert a word | O(L) |
One dictionary lookup/insert per character — walk or create L nodes, completely independent of how many other words are already stored. See Big-O Notation. |
| Search for an exact word | O(L) |
Walk L characters down from the root, then check one boolean flag. |
Search for a prefix (startsWith) |
O(L) |
Identical walk to search, just without checking isEndOfWord at the end. |
| Space |
O(total characters across all inserted words), worst case |
Shared prefixes are stored once — a trie with "car" and "care" uses 4 nodes, not 3 + 4 = 7. Worst case (no shared prefixes at all) approaches storing every word independently. |
The headline advantage over a Set<String>: a hash set's contains is O(L) too (it has to hash the whole string), but a Set cannot answer "does any stored word start with this prefix" without scanning every entry — O(n · L). A trie answers that in O(L), completely independent of n.
A trie is autocomplete made structural — every node is a shared prefix, every edge is one more typed character, and a flag (not a value) marks where a real word actually ends.
Suppose you insert "bat" into the trie from the example above (which already contains "cat", "car", "care", "dog"). Which existing nodes, if any, get reused, and which get newly created? Then explain: if you inserted 10,000 English words that all happened to share no common prefixes at all, how would the trie's total node count compare to storing those same words in a Set<String> — and why does that make a trie a poor choice when prefix sharing is low?