Drag across the tree. Click it, then use ← → to step and Space to play.
A trie stores strings one character per level, so words with the same beginning share a path: "car", "cat" and "cart" all hang off the same c → a. Each node maps characters to children and carries a flag for "a word ends here". Looking a word up never compares it to other words; it just walks its L characters down from the root, so insert, search and starts_with all cost O(L), no matter how many words are stored.
FIG. 16 · The board from page 6, where each gate holds one character and the root is the empty string. A thick ink ring means end_of_word: a whole word stops at that gate. The word being processed runs along the channel below, with its current letter in red. Red marks the gate the code is at, and ringed gates and lit grooves are the path walked so far. Callout: A root.
def insert(self, word):
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.end_of_word = True
def search(self, word):
cur = self._walk(word)
return cur is not None and cur.end_of_word
def starts_with(self, prefix):
return self._walk(prefix) is not None
def _walk(self, s): # follow s, or None if it breaks
cur = self.root
for c in s:
if c not in cur.children:
return None
cur = cur.children[c]
return cur
def search(self, word): # LeetCode 211: '.' matches any letter
def dfs(node, i):
if i == len(word):
return node.end_of_word
c = word[i]
if c == '.':
for child in node.children.values():
if dfs(child, i + 1):
return True
return False
if c not in node.children:
return False
return dfs(node.children[c], i + 1)
return dfs(self.root, 0)
def longestCommonPrefix(strs): # LeetCode 14, with a trie
trie = Trie()
for w in strs:
trie.insert(w)
cur, prefix = trie.root, []
while len(cur.children) == 1 and not cur.end_of_word:
c, cur = next(iter(cur.children.items()))
prefix.append(c)
return "".join(prefix)
Words: dad, bad, mad, bed. search(".ed"): a dot matches any letter, so at the root the search tries every child. 'd' has no 'e' below it, so it backtracks and tries 'b', where b → e → d ends a word. Answer: True. Trigger: "word dictionary".
["flower", "flow", "flight"]. Insert them all; the common prefix is the path down from the root while every node has exactly one child and no word has ended. It splits after "fl" (o / i). Answer: "fl". Trigger: "prefix".
| Operation | Time | Space | Why |
|---|---|---|---|
| insert(word) | O(L) | up to L new nodes | One node per character, created only where the path doesn't exist yet. |
| search(word), starts_with(prefix) | O(L) | O(1) | Walk L edges; independent of how many words are stored. |
| Whole trie | — | O(total characters) | At most one node per character inserted; shared prefixes are stored once. |
| Hash set of words (page 9) | O(L) to hash | O(total characters) | Fast for exact lookups, but "which words start with ca?" means checking every word. |
The path c → a exists because "car" and "cat" were inserted, but "ca" was not. Without the flag, search("ca") would wrongly say yes. The flag is the only difference between search and starts_with.
Every word below a node shares the prefix spelled by the path to it.
Many lookups against the same set of words.
class TrieNode:
def __init__(self):
self.children = {}
self.end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.end_of_word = True
def search(self, word):
cur = self._walk(word)
return cur is not None and cur.end_of_word
def starts_with(self, prefix):
return self._walk(prefix) is not None
def _walk(self, s): # follow s, or None if it breaks
cur = self.root
for c in s:
if c not in cur.children:
return None
cur = cur.children[c]
return cur