What it is
A trie, or prefix tree, stores strings one character per level, so words that start the same way share a path. It answers "is there anything starting with this?" in time that depends only on the prefix's length, no matter how many words you've stored.
How it works
Each node is a map from a character to a child node. Inserting walks down, creating nodes as needed, and marks where a word ends. Looking up walks the same way and stops if a character is missing.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for letter in word:
node = node.setdefault(letter, {})
node["$"] = True # A word ends here.
def _walk(self, text):
node = self.root
for letter in text:
if letter not in node:
return None
node = node[letter]
return node
def contains(self, word):
node = self._walk(word)
return node is not None and "$" in node
def starts_with(self, prefix):
return self._walk(prefix) is not NoneThe pieces don't have to be letters. A trie over bits, one bit per level, finds which network prefixes an IP address falls into. It's what routers use for longest-prefix matching.
Trade-offs
| Trie | Hash set | Sorted list | |
|---|---|---|---|
| Is this exact word there? | O(length) | O(length) to hash | O(log n) comparisons |
| Anything with this prefix? | O(length) | Check every word | Binary search, then scan |
| Memory | High: a node per character | Low | Low |
In an interview
- Look for prefixes, autocomplete, word games or searching many words at once.
- Use a dictionary for children unless the alphabet is small and fixed.
- Give time in terms of the word's length, not the number of words.
Worked example
A fast IP firewall
A firewall has thousands of rules like 'DENY 10.0.0.0/8' or 'ALLOW 10.1.2.0/24', and the first rule that matches an address wins. Checking every rule for every packet is too slow.
- A rule matches an address when the rule's first n bits equal the address's first n bits. So the rules that match an address are exactly the prefixes of that address's bits.
- Build a trie over bits: each level is one bit, so each node has at most two children, 0 and 1.
- Insert each rule by walking its first n bits and storing the rule's position in the list at the node where it ends. If two rules end at the same node, keep the earlier one.
- To check an address, walk its 32 bits from the top. Every node you pass that has a rule on it is a matching rule. Keep the one with the smallest position.
- For 10.1.2.5 with the two rules above: you pass the /8 node (rule 1) and later the /24 node (rule 2). The first rule in the list wins, so it's DENY.
- Each lookup is at most 32 steps no matter how many rules there are. Checking every rule would be O(rules) per packet.
- If no node on the path has a rule, fall back to the default, usually deny.
Follow-up questions
Things interviewers tend to ask once you've brought this up.
- How would you build autocomplete?
- Insert every search term with how often it's searched. Store the top five completions at each node, so typing a prefix returns them in one walk.
- How do you find many words in a grid at once?
- Put all the words in a trie and walk the grid and the trie together, stopping a path as soon as the trie has no child for the next letter.
- How do you support a wildcard like 'b.d'?
- When you hit the wildcard, try every child at that level. It's a small search, still cut short by the letters around it.
- How do you delete a word?
- Remove its end marker, then walk back up removing nodes that no longer have children or end markers.
Common mistakes
- Forgetting to mark where words end, so a prefix like 'car' counts as a word just because 'cart' exists.
- Making a 26-slot array per node when the alphabet isn't fixed.
- Giving complexity in terms of the number of words instead of the word length.
- Using a trie when a hash set would do, because you only ever need exact matches.
- Not mentioning memory, which can get big with long, varied strings.