In this article
Before you start
This page belongs to the coding interview patterns and method learning path, and it assumes only basic programming.
Why interviewers ask this
A trie question separates candidates who store strings from candidates who understand prefixes. Candidates report trie problems in several forms: implement a trie for a file system, merge two tries, find words on a letter board with a dictionary, and design a search autocomplete system. No public source behind this page ties any one of them to a named company, so treat them as candidate reports.
A weak answer keeps a list of words and scans all of it for every prefix. A strong answer walks the prefix one character at a time, knows why the cost depends on the length of the prefix and not on the number of words, and keeps a flag for complete words. A Staff-level answer adds the ranking rule, the memory cost of each node and the trade-off between storing counts and storing top results.
Trie ladder from first principles
- End-of-word flag
- An end-of-word flag is a marker on a trie node that records that the path from the root to this node is a stored word and not only the start of longer words, which is what lets a search tell "app" apart from a prefix of "apple".
- Hot degree
- Hot degree is the number of times a user typed exactly the same sentence before, the ranking score in the autocomplete problem LeetCode 642, which a trie stores as a count at the node where that sentence ends; ties are broken by American Standard Code for Information Interchange (ASCII) order, smaller first.
In plain words
Picture a road with forks. Each letter is a fork, and a word is the route you take from the start. Two words that begin the same way travel the same road until they split. The analogy breaks in one place: a route can end at a town in the middle of the road, which is why a stored word needs a marker, not just a position.
In one precise sentence: a trie turns a set of strings into a tree. Looking up a string means following one edge per character.
Wikipedia notes that unlike a binary search tree, nodes in a trie do not store their associated key. It adds that tries can work with any ordered sequence of elements, not only letters.
Step 1: Insert walks from the root and creates missing nodes
Insert adds one node per character that is not already on the path. Start at the root, and for each character of the word, follow the child for that character if it exists, or create it if not. The input is a word; the output is a path of nodes that now spells it.
Words that share a prefix reuse the nodes of that prefix, which is the whole saving. A second word beginning the same way costs nodes only for the part that differs. The work is one step per character, so the cost depends on the length of the word and not on how many words are already stored. You now know how the tree is built; the next step is the part that decides whether a lookup answers correctly.
Step 2: A flag separates a stored word from a prefix
The end-of-word flag separates a stored word from a prefix, and forgetting it is the classic error. A prefix is the first part of a string, so "app" is a prefix of "apple". After you insert only "apple", the path for "app" exists in the tree, yet "app" was never stored.
The LeetCode statement shows this exactly: after undefined, undefined returns false while undefined returns true, and after undefined, undefined returns true. The flag is therefore set on the last node of every inserted word. search walks the path and also requires the flag; startsWith only requires that the path exists.
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_word = True
def _walk(self, text):
node = self.root
for ch in text:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word):
node = self._walk(word)
return node is not None and node.is_word
def starts_with(self, prefix):
return self._walk(prefix) is not NoneThe helper _walk is shared, so the only difference between the two public checks is the flag test on the last line of search. A shorter treatment of just these three methods is in how to implement a trie in Python; this page goes on to ranked autocomplete. In the Python interview questions the same dict-of-children shape appears whenever a nested lookup is needed.
Step 3: Prefix search walks down, then collects everything below
Prefix search finds every stored word that starts with a typed prefix in two phases. The first phase walks to the prefix node, one step per character. The second phase collects every word beneath that node. The Sedgewick and Wayne slides show the same shape: walk to the prefix node with undefined, then collect the keys below it with undefined.
The cost has two parts. The walk costs as many steps as the prefix has characters, whatever the size of the dictionary. The collection costs in proportion to the number of nodes below the prefix node, because every one of them may be visited. If the prefix is a single letter that begins most words, collection touches most of the tree. In the worked example below, the prefix "i l" costs 3 walk steps and then 15 nodes below it.1
Step 4: Hot degree ranking turns prefix search into autocomplete
Autocomplete is prefix search plus a ranking rule. In the LeetCode 642 statement, as mirrored, hot degree is the number of times a user typed exactly the same sentence before, and the top three hot sentences come back with the hottest first. If several sentences have the same hot degree, ASCII order decides, smaller first. If fewer than three exist, return as many as you can. A special character such as "#" ends the sentence, so the answer is an empty list and the typed sentence is recorded.
Step-by-step description
- One node per new character.
- The flag on the second p marks a word.
- Walk to the prefix node, then collect.
- Hot degree first, then ASCII order.
- Insert adds one node per character not already on the path.
- The end-of-word flag separates a stored word from a prefix.
- Prefix search walks to the prefix node, then collects every word below it.
- Autocomplete ranks completions by hot degree, then ASCII order.
Insert adds one node per character not already on the path. The end-of-word flag separates a stored word from a prefix. Prefix search walks to the prefix node, then collects every word below it. Autocomplete ranks completions by hot degree, then ASCII order.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
The sentences and counts come from the LeetCode 642 statement: "i love you", "island", "iroman" and "i love leetcode", typed 5, 3, 2 and 2 times.1 Inserting them gives the numbers below.
| Quantity | Value |
|---|---|
| Characters in the four sentences | 37 |
| Trie nodes, root excluded | 28 |
| Nodes saved by shared prefixes | 9 |
| Nodes below the prefix "i" | 27 |
| Nodes below the prefix "i l" | 15 |
| Completions for "i" / for "i l" | 4 / 2 |
| Memory of 29 nodes with 27 child slots of 8 bytes (illustrative) | 6,264 bytes |
| Prefix of 5 characters, 1,000,000 stored sentences (illustrative) | 5 walk steps against 1,000,000 checks for a scan |
Text description of the diagram
- After four sentences the trie has 28 nodes for 37 characters inserted.
- Shared prefixes save 9 nodes.
After four sentences the trie has 28 nodes for 37 characters inserted, and shared prefixes save 9 of them.1 The first sentence adds 10 nodes. "island" adds 5, because only the letter "i" is shared. "iroman" adds 5 for the same reason, and "i love leetcode" adds 8, because "i love " already exists.1 The worst case is one node per character inserted, which is 37 here.
Now run the typing sequence from the statement. After "i", all four sentences match. The counts are 5, 3, 2 and 2, so the top three are "i love you", "island" and then one of the two sentences tied at 2. The space character sorts before "r" in ASCII order, so "i love leetcode" beats "iroman". After a space, only the two "i love" sentences remain, in the order "i love you" then "i love leetcode". After "a" the path "i a" does not exist, so the result is an empty list, and "#" also returns an empty list.1 These outputs match the example in the statement.
The memory row is an assumption, not a measurement: it takes 27 child slots (26 letters and a space) of 8 bytes each, which gives 216 bytes per node.1 An array per node makes each step fast but costs space even when most slots are empty.
Trade-offs and edge cases
A trie trades memory for prefix speed. It is not constant time: lookup costs at most as many steps as the key has characters, because a miss stops early. The LeetCode 208 constraints allow words of 1 to 2000 lowercase English letters, but that restriction belongs to the problem, since a trie works on any ordered sequence.
A hash set finds the words with a prefix by scanning every word. A trie finds them by walking to the prefix, then collecting below it. A hash set still wins when only whole-word lookups matter, because it stores one entry per word and has no per-character nodes. Visiting children in order gives sorted output when they sit in an array; with the dict of children used above, sort the keys first.
Text description of the diagram
- A hash set finds the words with a prefix by scanning every word.
- A trie finds them by walking to the prefix, then collecting below it.
A radix tree is a space-optimized trie in which each node that is the only child is merged with its parent, so edges carry strings and long single-child chains disappear. It saves nodes when words are long and branch rarely.
A common design choice for autocomplete, not part of the statement, keeps a pointer to the node for the text typed so far, so each keystroke advances one node, and stores the count at the node where a sentence ends. Each keystroke then collects the completions below the current node and sorts them by count, then by ASCII order.
Other edge cases: a design that stores the top results at every node answers a keystroke faster, but every insert must then update the lists along its path. Duplicate inserts must add to the count, not create a second entry. An empty prefix matches everything. Tree problems such as the lowest common ancestor share the same walk-from-the-root habit, and a heap-based top-k step, as in k closest points to origin, is the usual way to avoid sorting every completion.
How does a trie speed up a letter-board word search?
A trie speeds up a letter-board word search by letting one depth-first search (DFS) follow the board and the trie together, and stop as soon as the current path is not a prefix of any word. Put the dictionary in a trie. From each cell, step to an adjacent unused cell only if the current node has a child for that letter; otherwise the branch is dead and the search backs out.
When a node's flag is set, record the word and clear the flag, so the same word is not reported twice. Without the trie, every path would be checked against the whole dictionary. Deletion uses the same walk: unset the flag, then on the way back up remove each node that has no children and is not the end of another word.
How to answer it in an interview
How would you implement a trie, and how would you use it for autocomplete?
A trie is a tree where each edge is one character, so words that share a prefix share a path. Each node holds a map from character to child and an end-of-word flag. Insert and search walk one node per character, so they cost time proportional to the word's length, not to how many words I store. The prefix check is the same walk without the flag test. For autocomplete I walk to the typed prefix, collect the completions below it, and rank them by how often each was typed, breaking ties by ASCII order. The cost is memory for the child pointers.
The spoken structure: say what a trie is, say why the cost depends on length, separate search from the prefix check with the flag, then add the ranking and the memory cost.
Common mistakes
- "Search and startsWith are the same walk." (wrong) Search must also check the flag. (right) "
startsWithonly needs the path;searchneeds the path and the end-of-word flag." - "Each node stores its word." (wrong) The key is the path from the root. (right) "A node stores its children and a flag; the word is spelled by the path."
- "Autocomplete returns the first words found." (wrong) The statement requires ranking by hot degree with an ASCII tie-break. (right) "I collect the completions, sort by count descending, then by sentence, and return the top three."
- "A trie always saves memory." (wrong) Each node can carry a full array of child slots. (right) "A trie saves work on prefixes; I compress single-child chains with a radix tree if memory matters."
Follow-up questions
How do you design an autocomplete system with prefix frequency ranking?
Store past sentences in a trie with a count at each sentence end, advance one node per keystroke, collect the completions below it and return the top few by count, ties broken by ASCII order. Step 4 above shows the rule.
What is the difference between a trie and a radix tree?
A radix tree is a trie in which single-child chains are merged into one edge labelled with a string. It holds the same words with fewer nodes, at the price of more complex insert code.
Can a trie hold more than lowercase letters?
Yes. A trie works on any ordered sequence of elements, so digits, bytes or path segments of a file system can be the edge labels. With a dictionary of children no alphabet size is fixed in advance.
Why not scan a list of words for every prefix?
A scan checks every stored word, so its cost grows with the number of words. A trie walks as many steps as the prefix has characters, then visits only the nodes below it; the worked example compares 5 steps with 1,000,000 checks (illustrative).1
How would you merge two tries?
Walk both trees together from their roots. Where only one tree has a child, attach it whole (the two tries then share that subtree, so copy it if they will change independently); where both have it, recurse, and combine the flags and counts. The work is proportional to the nodes the two trees share. The recursion ladder walkthrough covers this walk-both-trees pattern.
- A trie stores strings as paths, one character per edge, so shared prefixes share nodes.
- The end-of-word flag is what separates search from the prefix check.
- Lookup costs time proportional to the key length, not to the number of stored words.
- Prefix search walks to the prefix node, then collects everything below it.
- Autocomplete ranks completions by hot degree, then ASCII order, and the cost is node memory.
Sources
- Trie — Wikipedia (accessed 2026-10-26), 26 Oct 2026
- Radix tree — Wikipedia (accessed 2026-10-26), 26 Oct 2026
- Implement Trie (Prefix Tree), problem 208 — LeetCode (accessed 2026-10-26), 26 Oct 2026
- LeetCode 642: Design Search Autocomplete System (statement as mirrored) — Medium mirror (accessed 2026-10-26), 26 Oct 2026
- LeetCode 642: Design Search Autocomplete System — LeetCode (accessed 2026-10-26), 26 Oct 2026
- Algorithms 4th edition: Tries lecture slides — Sedgewick and Wayne, Princeton (accessed 2026-10-26), 26 Oct 2026
