The Trie
A trie stores a set of words as one tree. The path from the root spells the word, so words that begin the same way share the same nodes and each shared beginning is stored only once. It costs memory, and it answers a question a hash table cannot: which stored words start with this prefix?
Why it exists: a hash table cannot answer "which words start with ca"
Search suggestions and input prediction all ask the same question about the beginning of a word.
Type ca into any search box and a list appears before you finish: cat, car, card, camera, cambridge. Input prediction, code completion in an IDE, and filtering contacts by last name all ask the same thing: given the beginning of a word, find every stored word that starts with it.
Chapter 6 covered the hash table, which is built for exact lookups. To check whether cat is in the dictionary it turns the whole word into one number and jumps to that slot. With respect to how many words are stored that is O(1) on average, although it still reads the whole word to compute the hash. The same computation is what makes prefixes hopeless: cat and car get unrelated hash values, and the table keeps no record that they share the letters ca. To list the words that start with ca it has to read all N stored words and compare the beginning of each one, which is O(N·L). The larger the dictionary, the slower the answer.
What gets lost: the structure between keys
A hash table is fast because it deliberately removes the relationship between keys. It answers equal and nothing else. A prefix is a relationship between keys. To answer prefix questions efficiently, the words have to be stored so that words with the same beginning sit in the same place. That is the whole motivation for a trie.
The idea is plain. Write cat, car, card one under the other. The first two letters, ca, are the same in all three, so store them once and let the paths separate after the a. Do this with ten thousand words and the result is a tree. Reading the characters along the path from the root down to any node gives a prefix. To find every word starting with ca, walk to the ca node: the whole subtree below it is the answer, and no other word is looked at.
Every edge carries one character, so reading from the root down to any node spells a prefix. A prefix query, which is awkward in most structures, becomes walking down a path.
Words that begin the same way share the same nodes. The more the words overlap at the front, as with natural-language words, URLs and file paths, the more nodes are shared. This is why it is also called a prefix tree.
Inserting or looking up one word costs its length L. Whether the tree already holds 10 words or 10 million does not enter that cost. §03 works through why.
Where the name comes from, and how it is said
Edward Fredkin introduced the term in 1960, taking it from the middle of the word retrieval. That creates a small problem: by its origin it should be said like "tree", but tree is already the name of another structure, so most people say "try" instead. You will hear both, and neither is worth arguing about. The structure is also called a prefix tree or a digital tree.
Inside a node: a table of children and one isEnd flag
What a single trie node holds, and why the boolean flag cannot be left out.
Start with a single node. A binary-tree node from chapter 7 holds a value, a left child and a right child. A trie node does not hold a value at all. It holds two things:
- children: a mapping from a character to a child node. A binary tree has exactly two children; a trie node has as many as the alphabet allows. For lowercase English that is at most 26, so children can be an array of length 26 (
TrieNode[26], index = letter − 'a') or a hash mapMap<Character, Node>. §03 compares the two. - isEnd: one boolean, answering a single question — does a stored word end exactly here?
One point is easy to miss: the character is not stored in the node. It is carried by the edge, or equivalently, a node is identified by the character its parent used to reach it. So the key is spelled by the path, not held by the node. The root stands for no character; it is the empty prefix every word starts from. Walking k edges down from the root reads k characters, which is a prefix of length k.
Why isEnd cannot be left out: cat and cattle
Suppose the trie holds cat and cattle. Because cat is the beginning of cattle, the t node reached by c-a-t still has a child, continuing with t, l, e. Now ask: is cat a stored word? Without isEnd there is no way to answer. Asking whether the node has children does not help — this one does have children, for cattle, and cat really is a word. And catt is reachable and also has a child, yet it is not a word. The node itself holds no word, so the answer has nowhere else to live: it has to be a flag on the node, isEnd = true, meaning a word ends here.
The lab below already holds five words. Insert a new word and watch which part of the path is reused, or look one up and watch the path light up node by node. Three endings are worth producing on purpose: a stored word matches, the string is a prefix but not a word, and the path stops partway.
Where tries are used
Tries sit behind autocomplete in search engines and input methods, behind longest-prefix matching in routers that forward IP packets, and behind spell checking. Databases and file systems usually use a compressed form, the radix tree (also called a Patricia trie): any chain of nodes with a single child is merged into one edge holding several characters, which removes most of the wasted nodes. The price is a more complicated insert, because adding a word can require splitting an existing edge in two. Redis uses a radix tree for stream IDs, and the Linux kernel used one for the page cache. Once the plain trie is clear, these are compressed versions of it.
Operations and cost: three methods, one walk
★ Core resultinsert, search and startsWith are all O(L) — L is the length of the string, not the number of stored words.
The three trie operations share one skeleton: start at the root and take the characters of the input string one at a time, moving down. They differ only in what happens when an edge is missing, and what is checked on arrival:
- insert(word): follow the characters, and create a node wherever the edge is missing. At the end, set
isEnd = trueon the last node. - search(word): follow the characters, and return false immediately if an edge is missing. On arrival, check isEnd on the last node; if it is false the string is only a prefix, not a stored word.
- startsWith(prefix): the same walk, but arriving is enough — isEnd is not read.
| Operation | Cost (L = length of the input string) | Why |
|---|---|---|
| insert(word) | O(L) | One step per character. Missing nodes are created along the way, at most L of them. |
| search(word) | O(L) | At most L steps to the end, then one check of isEnd. |
| startsWith(prefix) | O(L) | Walk to the last node of the prefix. isEnd is never read. |
| delete(word) | O(L) | Walk to the last node and clear isEnd. To reclaim memory, remove nodes bottom-up while they have no children and end no word. |
| every word starting with X | O(L + k) | O(L) to reach the prefix node, then a DFS over its subtree. k is the size of that subtree, so the cost follows the number of results, not the size of the trie. |
The cost does not depend on how many words are stored
Each step is one child lookup: an array index, or a hash-map lookup that is O(1) on average. The number of steps is L, the length of the string you passed in. Whether the dictionary holds 10 words or 50 million, looking up apple takes 5 steps. A hash table is also O(L) for one exact lookup, because it reads the whole key to compute the hash, so a trie is not faster at exact matching. What the trie adds is prefix search, and that is what it is chosen for.
The cost is memory: a fixed array of 26 vs a hash map
The speed is paid for in memory. Every character on every path needs a node, and every node needs a table of children. How that table is stored is the one real design decision in a trie:
The index is character − 'a', so reaching a child is one array read — the smallest constant factor available. Two costs come with it. Every node holds 26 pointers whether it uses them or not, which wastes a lot of memory when the words are sparse. And 26 only covers lowercase ASCII letters: input with digits, uppercase letters or non-ASCII text needs a different table. Good for practice problems that promise lowercase input.
Only the children that exist are stored, so sparse data costs far less memory, and any character can be a key: uppercase, digits, Chinese, anything outside ASCII. The price is a slightly larger constant factor per lookup than an array index. This is the safer default for real input.
Hash table vs trie
| Ability | Hash table (HashSet / HashMap) | Trie |
|---|---|---|
| Exact lookup: is this word stored? | ✓ O(L) on average — O(1) in the number of stored words, but the whole key is read to compute the hash | ✓ O(L) |
| Prefix query: which words start with X? | ✗ every stored key has to be read, O(N·L) | ✓ O(L) to the prefix node, then collect its subtree |
| List every word in alphabetical order | ✗ unordered, needs a separate sort | ✓ a DFS visiting children from a to z is already sorted |
| Memory | compact: one entry per word | shared beginnings save some, but one node per character plus a children table in each node costs more |
| Availability | built into the language | usually written by hand (§04) |
How to choose: if the question is only "is it there", use a hash table. As soon as the question mentions a prefix, a beginning or completion, use a trie.
Write a trie (this is LC 208)
Under 40 lines. The main version stores children in a hash map; each note gives the difference for the fixed 26-slot array.
The code below is a complete accepted answer to LeetCode 208, Implement Trie. The three methods share one private helper, find, which walks the path and returns nothing if an edge is missing. search and startsWith both call it and differ only in the last step. Read it once with the comments, then cover it and write insert from memory.
node.children.setdefault(c, Trie()) removes the if. Fixed array version: a list of length 26 indexed by ord(c) - ord('a').Check that you understood it (with the code covered)
1. Which single line is the difference between search and startsWith? (the && isEnd test) 2. Why does insert create a missing child while search returns nothing? 3. In the cost O(L), is L the length of the word or the number of words? If all three answers come quickly, LC 208 is yours.
Three languages: no built-in trie, only different children tables
None of the three standard libraries ships a trie, but each has a convenient container for children.
Unlike an array or a hash table, none of the three standard libraries contains a trie, so using one in an interview means writing it (§04). The comparison here is therefore not about APIs. It is about which container holds the children of one node, and what to watch out for in each language. The decision is the same one as before: a fixed-size array (fastest, wasteful, lowercase ASCII only) or a hash map (compact on sparse data, any character).
| Language | Two typical ways to hold children | What to watch out for |
|---|---|---|
| Java | TrieNode[] next = new TrieNode[26] (fast)or Map<Character, TrieNode> (general) | For the array, the index is c - 'a'. For the map, computeIfAbsent does "look up, or create and store" in one line. |
| Python | dict: self.children = {}or a list of length 26 | setdefault or defaultdict shortens insertion. The shortest version of all is a nested dict used as the whole tree, which is what the LC 212 solution below does. |
| JavaScript | Map (recommended)or a plain object Object.create(null) | A plain object inherits keys such as __proto__ from its prototype, so a lookup can return something that is not a child. Map avoids that and keeps insertion order. |
Does a trie actually save memory?
The intuition that shared prefixes save space depends on the data. When words overlap a lot at the front — natural language, URLs, file paths, phone numbers — folding the common beginnings does save space. When the words are short and share almost nothing, a trie costs more than storing the strings: one node per character, plus a children table in every node, with 26 pointers each in the array version. The pointer overhead can easily exceed the characters saved. Real systems therefore use the compressed forms — radix tree or double-array trie — which merge chains of single-child nodes into one edge, at the cost of a more complicated insert. The conclusion to keep: a trie is chosen for prefix queries, not to save memory.
Patterns: three problems that cover how a trie is used
★ Interview coreA: walk the template. B: a wildcard turns the walk into a DFS. C: the trie prunes a grid search.
Almost every trie problem is the LC 208 template plus one addition. A walks the template itself, frame by frame: how insertion reuses a prefix, and the three ways a lookup can end. B adds a wildcard to the query, which forces the walk to branch at a node and become a DFS. C combines the trie with backtracking on a grid, where the trie is used to cut off branches early. That is where a trie helps most.
LC 208 · Implement Trie (walking the template)
MEDIUMThe task: implement insert, search and startsWith. Brute force: keep every word in a HashSet<String>. search is O(L), but startsWith has to read every word in the set and compare its beginning, which is O(N·L) and fails once the dictionary is large. The answer is the trie from §04. Instead of repeating the code, run it: insert app, then insert apple to see the prefix reused, then four lookups that show all three possible endings.
Cost, and the follow-up questions
All three methods are O(L). The space is the number of nodes times the size of one children table, and the number of nodes is at most the total number of characters inserted. Follow-ups to expect: 1. What is the difference between startsWith and search? One isEnd test. 2. How do you delete a word? Walk to the last node and clear isEnd; to reclaim memory, remove nodes bottom-up while they have no children and end no word. 3. How do you count the words under a prefix? Keep a counter on each node and add one to every node along the path during insert (the idea behind LC 677).
LC 211 · Add and search words (the wildcard '.')
MEDIUMThe task: support addWord, and search where the string may contain '.', which matches any single letter. The difficulty: an ordinary character tells you which edge to take, but '.' does not, so every child edge has to be tried. A loop that recurses once per branch is a DFS with backtracking. The answer: addWord is LC 208 unchanged. search becomes recursive: an ordinary character descends into the one matching child; '.' loops over every child of the current node and recurses into each, returning true as soon as one succeeds.
any(...) stops at the first branch that returns True, so the remaining branches are never tried.LC 212 · Word Search II (using a trie to prune)
HARDThe task: given a grid of letters and a list of words, find every word that can be spelled by moving between adjacent cells (up, down, left, right) without using a cell twice. Brute force: run one grid search per word. With a few thousand words, many of which begin the same way, the search starting from a given c is repeated over and over, and the solution times out.
Why a trie helps: build one trie from all the words, then walk the grid once, moving down the trie in step with the DFS. Two things follow:
- One DFS tests many words at once. The
c-aspelled out on the grid is the beginning of cat, car and card at the same time, so one walk checks all of them instead of starting again for each word. - A missing edge ends the branch immediately, and that is the pruning. If the current letter has no child at the current trie node, no word starts this way, so every longer path from here is useless. Return at once and the whole branch disappears. This one check is what brings the search back into a workable range.
Two implementation details help. First, store the whole word on the node where it ends instead of only a boolean, so a match can be collected without rebuilding the string. Second, clear that field after collecting it, which removes duplicates without any extra bookkeeping.
'#', stores the word without colliding with a character key.The one sentence to remember
The grid is not searched once per word. One DFS over the grid follows the trie and tests every word on the way. The trie plays two parts: words that share a beginning share one path, and a beginning that no word has ends the branch at once. This is the general shape of multi-pattern matching. Taking it further leads to the Aho-Corasick automaton, which adds failure links to a trie so the search never has to restart.
Problem set: 8 trie problems
Grouped by patternFrom the template up to the 0/1 trie. Progress is stored in your browser. Think for 30 seconds before opening a hint.
Quiz
✎ QuizSix correct answers light this chapter green.
A trie holds 500,000 English words. Roughly how many steps does it take to check whether apple is one of them?
A trie already contains cat and cattle. What goes wrong if a node has no isEnd flag?
Which requirement is the clearest sign that you need a trie and a hash table will not do?
A node can store its children in a fixed array of 26 slots or in a hash map. Which statements are correct? (select all)
In one trie, what is the only difference between search(word) and startsWith(prefix)?
For maximum XOR of two numbers (LC 421), each integer is inserted into a special trie one bit at a time. Every node in that tree has only a 0 branch and a 1 branch. It is usually called a "____ trie". (write the two digits with a slash between them)
- A trie exists for one reason: a hash table turns the whole key into one number and loses the beginning of the key, so it cannot answer prefix questions. A trie keeps words with the same beginning on the same path, which turns "starts with X" into walking down that path.
- The structure is small: a node holds children (character to child node) and isEnd (a boolean). The characters sit on the edges, so the path spells the word and the node itself stores no word. isEnd is required: without it, cat cannot be told apart from the part of cattle that passes through the same nodes.
- insert, search and startsWith are all O(L), where L is the length of the string, not the number of words. This independence from the size of the dictionary is the point of the structure. search differs from startsWith by one
isEndtest. - The children table is the design decision: a fixed array of 26 is fastest but holds 26 pointers per node and only accepts lowercase ASCII; a hash map stores only the children that exist and accepts any character, with a slightly larger constant. A trie buys prefix queries with memory, not the other way round.
- Three patterns: the LC 208 template → LC 211, where a wildcard makes the walk branch into a DFS → LC 212, where the trie ends a grid branch as soon as the prefix does not exist. Add the 0/1 trie, which stores integers bit by bit, for maximum XOR. When a problem mentions prefixes, completion or a shared beginning, think of a trie.