Tries

The idea

A trie spells words out one letter per link

A trie, or prefix tree, stores a set of words as paths. Each node holds a map from a letter to the next node, and a flag that says whether a word ends there. The root stands for the empty string; every node below it stands for the prefix spelled by the letters on the way down.

car, cat and cart share the path c, a. A node stands for the prefix spelled on the way to it; three of them end a word.

The rule

Words that start the same way share the same path. Whatever you ask about a word or a prefix, you answer by walking one link per letter, so the cost depends on the word's length, never on how many words are stored.

In the pseudocode, TrieNode() makes a node with an empty children map and end set to false. The player draws the letters on the links and a dot under each node where a word ends.

Basic

Inserting follows existing letters and adds only what's new

To insert a word, start at the root and take one letter at a time. If the current node already has a link for the letter, follow it; if not, create a node. After the last letter, mark that node as a word's end.

The end flag matters: "car" ends in the middle of "cart", so reaching a node is not the same as finding a word.

Medium

One walk answers both "is it a word" and "is it a prefix"

Both questions walk the same path. If a letter's link is missing, the answer to both is no. If the walk gets to the end, a prefix question is answered yes straight away, because some word continues from there. A whole-word question also needs the last node's end flag.

A hash set of the words could answer the whole-word question just as fast. It can't answer the prefix question without looking at every stored word.

Hard

A wildcard turns the walk into a search with backtracking

When a pattern has a dot that matches any letter, there is no single link to follow. Try each link out of the current node in turn, recursively, and stop at the first one that leads to a full match. A branch that fails returns false, and the loop moves on to the next letter: backtracking over the tree's branches.

The cost

Time per letter, memory per distinct prefix

Question	A hash set of words	A trie
Is this exact word stored?	O(L) on average, to hash it	O(L)
Which words start with this prefix?	Check every word: O(total letters)	O(p) to reach the prefix, then only the matching words
Memory	Each word stored once	One node per distinct prefix, each with its own map

L is the length of the word asked about and p the length of the prefix. The memory is the trie's weakness: a node per letter, each holding a map, uses several times the space of the words themselves. A fixed array of 26 links per node is faster than a map for lowercase words, and wastes most of its slots. Compressed tries, which merge every chain of single-child nodes into one link labeled with several letters, save much of that space.

In practice

Prefix questions are where a trie pays off

Autocomplete, spell checkers and word games all ask prefix questions: what can follow what has been typed, and is this a word yet. The same structure works on anything that can be spelled out one symbol at a time. For whole numbers, a trie over their binary digits finds, for a given number, the stored number that differs from it in the highest digits first.

Check yourself

3 questions

1. Why does each trie node need an end flag?

2. A trie holds a million words. How long does checking a 6-letter word take?

3. Which question can a trie answer that a hash set of words can't answer efficiently?

Takeaways

Remember this

A trie (prefix tree) stores words as paths of letters; words that start the same way share nodes.
Insert, lookup and prefix checks all cost O(L) for a word of L letters, however many words are stored.
A node's end flag separates whole words from prefixes of longer words.
Wildcards turn the walk into backtracking: try each branch and stop at the first that matches.
The price is memory: one node per distinct prefix, each with its own map.

Practice

Now solve some yourself

Mixed with topics you have practiced 0 unlocked

4 more once you have practiced Bit manipulation, Recursion & backtracking, Dynamic programming: basics. Play one of its examples to the end and solve one of its problems to unlock them.

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.