Standard Trie (and When Not to Use One)

A trie (prefix tree) stores strings character by character, so words that share a prefix share the path for it. Walking down one node per character answers "is this a word?" and "does any word start with this?" in time proportional to the length of the query, no matter how many words are stored. It's the tool for prefix questions; for plain membership, a hash set is usually better.

The idea#

Each node holds a map from character to child and a flag that says "a word ends here". Inserting a word walks down its characters, creating missing children, and sets the flag at the last node. Searching walks the same path:

Whole-word search succeeds only if the path exists and the last node is flagged, so inserting apple does not make app a word.
Prefix search succeeds as soon as the path exists; the flag doesn't matter.

A trie holding app, apple, apply and bat. The path a, p, p is shared; the second p is marked as a word end, with children l, then e and y, both word ends. A separate branch b, a, t ends at a marked t

Each operation is one walk down the tree, so its cost depends on the length $L$ of the word, not on how many words are stored.

Operation	Time	Why
Insert	$O(L)$	one step per character of the word
Search	$O(L)$	one node per character
Starts with	$O(L)$	the same walk, without checking the end flag

Space is $O(T)$ , where $T$ is the total number of characters inserted, minus whatever is shared.

The flag is one kind of marker. For other problems, store what the search needs inside the node: a count of words passing through, the word itself, a running sum, or a short list of suggestions. Then decide while walking, using those markers.

How to spot it#

Reach for a trie when the question is about prefixes over many strings.

"Starts with", "prefix", "autocomplete", "suggestions".
Many words with shared beginnings, and many queries against them.
Replacing a word with its shortest dictionary root.
Searching a grid or pattern where you want to stop as soon as no word can match.

When a trie is the wrong tool#

Prefix signals can mislead you, because a trie has real costs. In these situations they are not worth paying:

Situation	Why the trie loses	Use instead
Only exact lookups	A hash set is also $O(L)$ , with far less overhead	`set`
Memory is tight	Every node carries its own child map	`set` or a sorted list
Few, short strings	Nodes are scattered in memory, so lookups miss the cache	sorted list + binary search
Little shared prefix	No sharing means a sparse tree of mostly wasted nodes	`set`

The simple rule: need prefix operations, use a trie; only need exact matches, use a hash set. Longest Common Prefix (LC 14) is a good example of a problem that looks like trie territory but isn't. Its hint below says why.

Template#

Here are insert and both searches, with the node layout from "The idea". Notice that one shared walk serves both kinds of search.

node: children = empty map, is_end = false
insert(word):
    node = root
    for each ch in word:
        if ch not in node.children: create a child for ch
        node = node.children[ch]
    node.is_end = true                 # marker: a word ends here
walk(s):                               # the node for s, or nothing
    node = root
    for each ch in s:
        if ch not in node.children: return nothing
        node = node.children[ch]
    return node
search(word): walk(word) exists and its is_end is true
starts_with(prefix): walk(prefix) exists

A map for the children means the alphabet does not need to be fixed. Create a child only when it is missing.

Pitfalls#

These mistakes cause the most wrong answers.

Treating a prefix as a word. search must check the end marker; starts_with must not.
Overwriting an existing child. Creating a new child without checking first discards everything below it. Check for the key, or use setdefault.
Using a trie for exact membership. If no prefix question is ever asked, a set is simpler and smaller.
Clumsy build orders. When a word must be built from shorter words, sorting and inserting one by one while checking end flags is awkward. Build the whole trie first, then walk it.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Implement Trie (Prefix Tree)

Write the shared walk once. search is the walk plus the end flag; starts_with is the walk alone.

Hint: Longest Word in Dictionary

Insert every word first. Then DFS from the root, but step only into children whose is_end is true. The deepest node reached is the answer; break ties by the smaller word. For small inputs, a set of words that checks every prefix also works.

Hint: Replace Words

Walk each sentence word down the trie of roots. Stop at the first node with an end marker: that is the shortest root. No marker on the path means the word stays as it is.

Hint: Map Sum Pairs

Store a running sum at every node: the total value of keys that pass through it. A prefix query is then one walk and one read. When a key is inserted again, add only the difference from its old value.

Hint: Extra Characters in a String

This is string DP over positions. From each position i, walk the trie forward and stop the moment no dictionary word continues. That replaces testing every substring.

Hint: Longest Common Prefix

This looks like trie territory, but it isn't. Compare the strings column by column and stop at the first mismatch. It is simpler and as fast.

Key takeaways#

A trie shares prefixes, so insert, search and prefix checks are $O(L)$ regardless of how many words are stored.
Whole-word search checks the end marker; prefix search doesn't.
Store whatever the problem needs in the node: a flag, a count, a word, a sum, suggestions.
Need prefix operations? Trie. Only exact matches? Hash set.

Core idea#

A trie (prefix tree) stores strings character by character, so words that share a prefix share its path. Insert, search and prefix checks take $O(L)$ , no matter how many words it holds. Use it for prefix questions. For plain membership, a hash set is usually better.

Key points#

Each node holds a map from character to child and an is_end flag.
Whole-word search needs the path and the end flag. Inserting apple does not make app a word.
Prefix search needs only the path.
Space is $O(T)$ for $T$ inserted characters, minus what is shared.
The flag is one kind of marker. A node can also hold a count, the word, a sum or suggestions.
Shortest root: stop at the first node with an end marker.
Longest word built letter by letter: DFS only into children with is_end true.
String DP: walk the trie forward from each position and stop when no word continues.

When not to use a trie#

Situation	Use instead
Only exact lookups	`set` (also $O(L)$ , less overhead)
Tight memory	`set` or a sorted list
Few, short strings	sorted list + binary search
Little shared prefix	`set`

Template#

insert(word):
    node = root
    for each ch in word:
        if ch not in node.children: create a child for ch
        node = node.children[ch]
    node.is_end = true
walk(s):                               # the node for s, or nothing
    node = root
    for each ch in s:
        if ch not in node.children: return nothing
        node = node.children[ch]
    return node

search is the walk plus is_end. starts_with is the walk alone.

Pitfalls#

Treating a prefix as a word. search checks the end marker. starts_with does not.
children[ch] = Node() without a check. It discards everything below. Check for the key first.
A trie for exact membership only. A set is simpler and smaller.
Longest Common Prefix looks like trie work. Comparing columns is simpler.

Say it in an interview#

"Prefix operations need a trie. Exact matches need only a hash set."
"Each operation is O(L) in the query length, not in the number of words."