Trie

Trie Patterns

A trie stores strings by their prefixes, so words sharing a start share nodes. That single property is what a hash map cannot offer: a hash of a word tells you nothing about words beginning the same way. Whenever a problem involves prefixes, autocomplete, or testing many words against the same input, a trie is usually the intended answer.

2 patterns6 techniquesJava code

Where to start, and what comes next

01
Basic Trie
Insert, search and prefix search. The whole structure is here, including the end-of-word flag that separates a stored word from a prefix.
Insert & Search Prefix Search (startsWith)Autocomplete
02
Advanced Trie
Wildcards, the bit trie for maximum XOR, and using a trie to drive a grid search. Each is the basic structure with one addition.
Word Search II Max XOR (Bit Trie)Wildcard Search

If you only have time for three things

The end-of-word flag, without which every prefix of a stored word looks like a stored word.
Using a trie to prune a search, which is what turns word search from one grid traversal per word into a single traversal for all of them.
The bit trie, where numbers are stored as fixed-length paths of bits so that maximum XOR becomes a greedy walk.

In an interview

The recognition is the test. If a problem gives you a list of words and something to match them against, consider a trie before writing a loop over the list. Be ready for the space question too: an array-of-26 node costs memory whether or not the children exist, and a HashMap node trades some speed to avoid that.

The idea underneath

Use a trie when you need prefix-based operations that hash maps can't do efficiently, like 'find all words starting with X' or 'find word matching pattern with wildcards'.

Problems that use these patterns

Implement TrieWord Search IIDesign Add and Search WordsReplace WordsMaximum XOR of Two Numbers

Questions people ask

Trie or hash map?

A hash map is faster for exact lookups and cannot answer anything about prefixes. If the question involves prefixes, autocomplete, or matching many words at once, that is the trie's territory. If it is pure membership, use the map.

How much memory does a trie use?

With an array of 26 children per node it is O(total characters times 26) in the worst case, since every node reserves all slots. A HashMap per node only stores the children that exist, which is much smaller on sparse data at some cost in constant factor.

Why does the maximum XOR problem use a trie?

Because storing each number as a path of bits turns the search for the best partner into a walk. At each bit you prefer the opposite of your own, since setting a higher bit is worth more than every lower bit combined, and that greedy walk is O(32) rather than a scan of every pair.