After this lesson, you will be able to: Understand what a trie is, where it is used (autocomplete, spell check, IP routing), and implement a basic trie with insert and search.
A trie (pronounced 'try') is a tree built for strings, keyed by characters. It makes prefix queries fast, which is why it powers autocomplete and spell checkers. It is the specialized structure that rounds out this sub-track.
A trie stores strings by their characters. Each node represents one character, and a path from the root spells out a prefix. Words that share a prefix share the same path until they diverge. To check if 'cat' is stored, you walk c then a then t and see if that path exists and ends at a marked word. Lookup time depends on the length of the word, not how many words are stored, which is the trie's key advantage.
Each node holds a map of children and a flag for end-of-word.
class TrieNode:def __init__(self):self.children = {} # char -> TrieNodeself.is_word = Falseclass Trie:def __init__(self):self.root = TrieNode()def insert(self, word):node = self.rootfor ch in word:node = node.children.setdefault(ch, TrieNode())node.is_word = Truedef search(self, word): # exact word matchnode = self._walk(word)return node is not None and node.is_worddef starts_with(self, prefix): # any word with this prefix?return self._walk(prefix) is not Nonedef _walk(self, s):node = self.rootfor ch in s:if ch not in node.children:return Nonenode = node.children[ch]return node
A hash set can tell you if an exact word exists in O(1), but it cannot answer 'give me every word starting with cat' without scanning everything. A trie answers prefix queries by walking to the prefix node and then collecting everything below it. That is why autocomplete uses tries: as you type, it walks one more character down the trie and the candidate words are the subtree underneath.
Forgetting the is_word flag and treating any reachable node as a complete word (then 'ca' matches when only 'cat' was inserted). Confusing search (exact word, needs is_word) with starts_with (prefix only). Underestimating memory: one node per character per branch adds up; consider a compressed trie (radix tree) for huge datasets. Reaching for a trie when a hash set would do, because you only ever need exact-match lookups.
Sign in and purchase access to unlock this lesson.