Module 19
Trie
A tree of characters: insert and search in O(word length), prefix counts, autocomplete, wildcard search, word grids and the binary trie for XOR.
A trie (say "try", from the word "retrieval") stores strings by sharing their prefixes: "car", "cat" and "cart" all walk through the same c → a nodes. Looking up a word or a prefix costs O(length of the word), no matter how many words are stored, and prefix questions that are awkward with a hash map become a single walk.
This module builds the trie, adds prefix counts for autocomplete, combines it with DFS for wildcards and word grids, and finishes with the binary trie, which stores numbers bit by bit to answer maximum-XOR questions.
Best after: Binary Trees, Strings
Part 1
Learn the ideas
- 19.1Building a TrieEach node has up to 26 children (one per letter) and a flag marking the end of a word. Insert and search walk one node per character.14 min
- 19.2Prefix Counts and AutocompleteStore how many words pass through each node, or the best few suggestions at each node, and prefix questions become one walk.10 min
- 19.3Trie + DFS: Wildcards and Word GridsWhen a query branches (a wildcard character, or a path through a grid), explore the trie with DFS and prune as soon as no child matches.12 min
- 19.4The Binary Trie for XORInsert numbers bit by bit from the highest bit; to maximise XOR with x, prefer the opposite bit at every level.10 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
The trie itself: insert, search and startsWith.
Wildcard search: DFS over every child at a
..Search many words at once by walking a trie alongside a grid DFS.
Shortest-prefix lookup: stop at the first end-of-word node on the path.
DFS over a trie, moving only through nodes that end words.
Autocomplete: up to three sorted suggestions per typed prefix.
The binary trie: greedy choice of the opposite bit from the top down.