Tries (Prefix Trees)

A trie (say “try”, from retrieval) is a tree specialized for one job: storing a set of strings so that prefix operations — “does any word start with prepre?” — are as fast as looking up a single word.

What you’ll learn

The trie shape: each node is a map of character -> child nodecharacter -> child node, plus an is_endis_end flag.
Why insert/search/startsWithstartsWith are all $O(L)$ — where LL is the length of the word, not the number of words stored.
The memory tradeoff: tries trade space for that prefix speed.
A complete, runnable TrieTrie class you can reuse directly.

The shape of a trie

Instead of storing whole words, a trie stores them letter by letter, sharing common prefixes as a single path. Insert "cat""cat", "car""car", and "dog""dog" and you get:

diagram A trie holding cat, car, dog mermaid

  graph TD
    root((root)) --> c((c))
    root --> d((d))
    c --> ca((a))
    ca --> cat(("t*"))
    ca --> car(("r*"))
    d --> do((o))
    do --> dog(("g*"))

catcat and carcar share the c -> ac -> a path — the trie only branches where the words actually differ. Nodes marked with ** are end-of-word markers: catcat and carcar are complete words, but cc and caca alone are just prefixes that happen to be shared.

Building it: a dict of children + an end flag

The simplest, most Pythonic trie node is just a dictdict mapping each character to its child node, plus a boolean for “a word ends here”:

trie_node.py

class TrieNode:
    def __init__(self):
        self.children = {}     # char -> TrieNode
        self.is_end = False    # True if a word ends at this node
 
 
# Manually build the cat/car/dog trie from the diagram
root = TrieNode()
for word in ["cat", "car", "dog"]:
    node = root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
    node.is_end = True
 
# Walk down "ca" and see both children waiting
ca_node = root.children["c"].children["a"]
print("children after 'ca':", sorted(ca_node.children.keys()))
print("'ca' itself a full word?", ca_node.is_end)

trie_node.py

class TrieNode:
    def __init__(self):
        self.children = {}     # char -> TrieNode
        self.is_end = False    # True if a word ends at this node
 
 
# Manually build the cat/car/dog trie from the diagram
root = TrieNode()
for word in ["cat", "car", "dog"]:
    node = root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
    node.is_end = True
 
# Walk down "ca" and see both children waiting
ca_node = root.children["c"].children["a"]
print("children after 'ca':", sorted(ca_node.children.keys()))
print("'ca' itself a full word?", ca_node.is_end)

A complete, reusable `TrieTrie` class

Wrap that pattern into insert/search/startsWithstartsWith — the exact three methods LeetCode’s “Implement Trie” problem asks for:

trie_class.py

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
 
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
 
    def _walk(self, prefix):
        """Return the node at the end of `prefix`, or None if it's absent."""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node
 
    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end
 
    def starts_with(self, prefix):
        return self._walk(prefix) is not None
 
 
trie = Trie()
for word in ["cat", "car", "dog", "do"]:
    trie.insert(word)
 
print("search 'cat':      ", trie.search("cat"))       # True -- full word
print("search 'ca':       ", trie.search("ca"))        # False -- only a prefix
print("starts_with 'ca':  ", trie.starts_with("ca"))   # True -- cat/car both start with ca
print("starts_with 'do':  ", trie.starts_with("do"))   # True
print("search 'dogs':     ", trie.search("dogs"))      # False -- never inserted

trie_class.py

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
 
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
 
    def _walk(self, prefix):
        """Return the node at the end of `prefix`, or None if it's absent."""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node
 
    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end
 
    def starts_with(self, prefix):
        return self._walk(prefix) is not None
 
 
trie = Trie()
for word in ["cat", "car", "dog", "do"]:
    trie.insert(word)
 
print("search 'cat':      ", trie.search("cat"))       # True -- full word
print("search 'ca':       ", trie.search("ca"))        # False -- only a prefix
print("starts_with 'ca':  ", trie.starts_with("ca"))   # True -- cat/car both start with ca
print("starts_with 'do':  ", trie.starts_with("do"))   # True
print("search 'dogs':     ", trie.search("dogs"))      # False -- never inserted

Every operation walks at most LL characters — one hop per letter — so all three run in $O(L)$ , completely independent of how many other words share the trie.

The memory tradeoff

A trie’s speed comes from sharing prefixes, but every distinct character transition still needs its own node. Storing nn words of average length LL costs up to $O(n \cdot L)$ nodes in the worst case (no shared prefixes at all) — often more memory than just keeping the words in a setset (which is $O(n \cdot L)$ total characters, but with far less per-character overhead from Python object/dict headers). The payoff is that prefix queries — “how many words start with prepre?”, autocomplete, spell-check — are not possible in $O(L)$ with a plain setset at all; you’d have to scan every word.

Complexity at a glance

Operation	Time	Notes
`insert(word)insert(word)`	$O(L)$	`LL` = length of `wordword`
`search(word)search(word)`	$O(L)$	independent of `nn` (word count)
`starts_with(prefix)starts_with(prefix)`	$O(L)$	same — the whole point of a trie
Space	up to $O(n \cdot L)$	less if words share prefixes heavily

LeetCode problem set

#	Problem	Difficulty	The twist
208	Implement Trie (Prefix Tree)	Medium	Exactly the class built above
212	Word Search II	Hard	Build a trie of the dictionary first, then DFS the board while walking the trie in lock-step, pruning any path the trie doesn’t contain
648	Replace Words	Medium	For each sentence word, walk a trie of “roots” and stop at the first `is_endis_end` you hit — the shortest matching root replaces the word

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 720 — Longest Word in Dictionary · Medium

Problem. Return the longest word in wordswords such that every prefix of it is also in wordswords. If several tie, return the lexicographically smallest. If none qualifies, return """".

Constraints. 1 <= len(words) <= 10001 <= len(words) <= 1000, 1 <= len(words[i]) <= 301 <= len(words[i]) <= 30, lowercase.

Examples. ["w","wo","wor","worl","world"]["w","wo","wor","worl","world"] gives "world""world" · ["a","banana","app","appl","ap","apply","apple"]["a","banana","app","appl","ap","apply","apple"] gives "apple""apple" · ["abc","bc"]["abc","bc"] gives """"

Editorial

Two requirements interact: length (longest wins) and order (lexicographically smallest breaks ties). Iterating in sorted order and only replacing on a strictly longer word satisfies both — among equal-length candidates the first one seen is the smallest, and it is never displaced.

Time $O(\sum |w|)$ roughly — each word’s prefixes are checked once, plus $O(n \log n)$ for the sort. Space $O(\sum |w|)$ for the set.

["a","banana","app","appl","ap","apply","apple"]["a","banana","app","appl","ap","apply","apple"] is the discriminating case: "apply""apply" and "apple""apple" both qualify at length 5, and the answer is "apple""apple" because it sorts first. Using >=>= instead of >> would return "apply""apply".

["abc","bc"]["abc","bc"] gives """" — "abc""abc" needs "a""a" and "ab""ab", neither present.

The trie version is the more idiomatic answer for this page: insert every word, then DFS from the root, descending only into children that are themselves complete words. That naturally explores only valid prefix chains, and visiting children in alphabetical order gives the tie-break for free. It is $O(\sum |w|)$ with no sort.

Follow-ups: “Do it with a trie?” — as above; the expected answer if the interviewer is testing this page’s structure. “Longest word built from other words (LC 472)?” — different: concatenation rather than prefixes, needing DP. “Why sort?” — for the tie-break; a trie replaces it with ordered child traversal.

LC 677 — Map Sum Pairs · Medium

Problem. Implement MapSumMapSum with insert(key, val)insert(key, val) and sum(prefix)sum(prefix), which returns the total of all values whose keys start with prefixprefix. Inserting an existing key overwrites its value.

Constraints. 1 <= len(key), len(prefix) <= 501 <= len(key), len(prefix) <= 50, 1 <= val <= 10001 <= val <= 1000, up to 5050 calls.

Examples. insert("apple", 3)insert("apple", 3), sum("ap")sum("ap") gives 33, insert("app", 2)insert("app", 2), sum("ap")sum("ap") gives 55, insert("apple", 1)insert("apple", 1), sum("ap")sum("ap") gives 33

Editorial

At only 50 calls with keys up to 50 characters, a dict plus a linear scan is comfortably fast and obviously correct. Start there.

Time $O(1)$ insert, $O(\text{keys} \times |\text{prefix}|)$ per sum. Space $O(\text{total key length})$ .

The overwrite rule is the real content. insert("apple", 1)insert("apple", 1) after insert("apple", 3)insert("apple", 3) must replace the 3, so sum("ap")sum("ap") drops from 5 to 3. A solution that adds to the existing value returns 6.

That rule is also what makes the obvious trie optimisation subtle. If each trie node stores a running total along the path, an overwrite must propagate the delta (new - oldnew - old), not the new value — which means you must remember the previous value anyway:

python

delta = val - self.values.get(key, 0)
self.values[key] = val
# then add `delta` to every node along the path

python

delta = val - self.values.get(key, 0)
self.values[key] = val
# then add `delta` to every node along the path

That gives $O(|\text{key}|)$ insert and $O(|\text{prefix}|)$ sum, independent of how many keys are stored. Worth offering as the scaling answer, and the delta detail is what an interviewer is listening for.

Follow-ups: “Make sumsum independent of the key count?” — the trie with running totals and delta updates. “Support deletion?” — insert a value of 0, or subtract the stored value along the path. “Sum over a key range rather than a prefix?” — a sorted structure or a Fenwick tree over sorted keys.

LC 1268 — Search Suggestions System · Medium

Problem. Given productsproducts and a searchWordsearchWord, return, for each successive prefix of searchWordsearchWord, the three lexicographically smallest products sharing that prefix.

Constraints. 1 <= len(products) <= 10001 <= len(products) <= 1000, 1 <= len(searchWord) <= 10001 <= len(searchWord) <= 1000, lowercase letters.

Examples. products = ["mobile","mouse","moneypot","monitor","mousepad"]products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"searchWord = "mouse" gives [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]][["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]

Editorial

Sorting up front converts “the three lexicographically smallest matches” into “the first three matches”, which a single scan plus a [:3][:3] slice answers.

Time $O(n \log n)$ for the sort, then $O(n \times |\text{searchWord}|)$ for the scans. Space $O(n)$ .

[:3][:3] handling short results is why the last three rows have only two entries — "mouse""mouse" and "mousepad""mousepad" are the only matches, and no padding is needed.

At these constraints the repeated scanning is fine. The two better approaches, both worth naming:

Trie with cached suggestions. Insert all products, and at each node store (up to) the three smallest words beneath it. Each query prefix is then an $O(|\text{prefix}|)$ walk with the answer already sitting at the node — which is exactly the autocomplete use case a trie exists for.
Two pointers over the sorted list. Narrow a [left, right][left, right] window as the prefix grows, since matches for a longer prefix are always a sub-range of the matches for a shorter one. $O(n \log n)$ total with no re-scanning.

Follow-ups: “Do it with a trie?” — the expected answer on this page; describe the cached-suggestions node. “Return kk suggestions instead of three?” — change the slice, and the cache size. “Products added dynamically?” — the trie handles inserts in $O(|\text{word}|)$ , whereas re-sorting is $O(n \log n)$ .

Recap

A trie node is a dictdict of character -> childcharacter -> child plus an is_endis_end flag — that’s the entire data structure.
Insert, search, and starts_withstarts_with are all $O(L)$ : one hop per character, independent of how many words are stored.
The cost is memory — shared prefixes save space, but divergent words each need their own node chain.
Reach for a trie specifically when the problem needs prefix-aware queries; for plain exact-match membership, a setset is simpler and often leaner.

Next: Graph Representations — adjacency lists, adjacency matrices, and edge lists, the building blocks BFS/DFS run on top of.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Tries (Prefix Trees)

What you’ll learn

The shape of a trie

Building it: a dict of children + an end flag

A complete, reusable TrieTrie class

The memory tradeoff

Complexity at a glance

LeetCode problem set

Practice — real LeetCode problems

LC 720 — Longest Word in Dictionary · Medium

LC 677 — Map Sum Pairs · Medium

LC 1268 — Search Suggestions System · Medium

Recap

Was this page helpful?

A complete, reusable `TrieTrie` class