What you'll learn
Quick Answer
A trie stores strings character by character in a tree, so shared prefixes share nodes. Lookup takes time proportional to the word length regardless of how many words are stored, and prefix search is the operation it exists for.
The problem a hash set cannot solve
Put a hundred thousand words in a set and asking "is car present?" is instant.
Now ask "which words start with ca?" The set has no idea. Hashing deliberately scatters similar strings, so car and card are nowhere near each other. Your only option is to check every word — a hundred thousand comparisons for every keystroke.
A trie stores words by their characters, so everything starting with ca lives under one node. Prefix search becomes: walk to that node, then collect what is below it.
It is nested dictionaries
In Python the simplest useful trie is a dictionary of dictionaries:
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node['$'] = True # marks end of a wordsetdefault returns the existing child if present and creates it otherwise, which is the entire insert in one line.
The '$' marker matters more than it looks. Without it you cannot distinguish a stored word from a prefix of one — after inserting card, the path for car exists even if car was never inserted. The marker records "a word ends here".
Inserting cat, car, card and dog shares the c-a path between the first three, and car is entirely contained within card's path.
Search and prefix search
def search(self, word):
node = self.root
for ch in word:
if ch not in node:
return False
node = node[ch]
return '$' in node
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node:
return False
node = node[ch]
return Truet.search("car") # True
t.search("ca") # False -- a prefix, not a stored word
t.starts_with("ca") # True
t.starts_with("cx") # FalseThe two methods are identical except for the last line, which is precisely the distinction the '$' marker exists to make.
For autocomplete you extend starts_with to return the node, then walk everything beneath it collecting words — a depth-first traversal of a subtree that is usually small.
Why it scales the way it does
Search takes O(L) where L is the length of the word — independent of how many words are stored. Looking up a five-letter word takes five steps whether the trie holds a hundred words or ten million.
That is the property worth stating in an interview. A hash set is also roughly O(L) because it must hash the string, so for pure lookup they are comparable. The difference is entirely in prefix operations, which the trie does in O(L) and the set cannot do at all.
The cost is memory. Every character is a node, and in Python each node is a dictionary with substantial overhead. A trie of a large dictionary can use considerably more memory than the strings themselves. Compressed variants such as radix trees merge single-child chains to reduce this.
When to use one
Good fits: autocomplete and type-ahead search, spell checking and suggestions, IP routing tables (longest prefix match), and word games where you must check whether a partial word can still become valid — which lets you prune a search early.
Poor fits: exact lookup only, where a hash set is simpler and smaller; small datasets, where scanning a list is fine; and cases where memory is tight.
In interviews the trie usually appears for autocomplete, word search on a grid combined with backtracking, or "find the longest common prefix". Recognising that a problem involves prefixes is the signal — that word is nearly always the hint.
Related: the same prefix-sharing idea underlies how Huffman coding builds its code tree, though it is built by frequency rather than by characters.