Trie Design
What is this?
A trie is a filing cabinet where the drawers are letters. To file card you open drawer c, then a, then r, then d, and mark that last drawer "a word ends here". Everything beginning car shares the first three drawers, which is why the structure is compact and why asking "is there anything filed under car?" takes three steps regardless of how many words exist.
This chapter builds that, then stretches it twice: once by allowing a wildcard in the query, and once by noticing that the drawers do not have to be letters.
Fun fact: Design In-Memory File System is a trie in disguise, and seeing that collapses it from a fiddly design problem into about twenty lines. A path is a list of components, a directory is a node whose children are its entries, and a file is a node carrying content instead of children.
lsthen becomes "return this node's children, sorted". The problem states the sorting requirement, so sorting on read (or keeping an ordered map) is a deliberate choice worth mentioning.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
The idea: a node holds a map from label to child plus a flag saying whether a key ends here. Exact lookup follows one label per step; a wildcard follows all of them; and the labels can be any unit you like.
1. The structure
class Node:
def __init__(self):
self.children = {} # label -> Node
self.is_end = False # a complete key finishes here
def insert(root, word):
node = root
for ch in word:
node = node.children.setdefault(ch, Node())
node.is_end = True
is_end is not optional. Without it a trie containing card would report car as present, because the path exists. The flag is what separates "a key ends here" from "a key passes through here".
2. Wildcards mean branching
def search(node, word, i):
if i == len(word):
return node.is_end
ch = word[i]
if ch == '.':
return any(search(child, word, i + 1) for child in node.children.values())
return ch in node.children and search(node.children[ch], word, i + 1)
A concrete character narrows to one child; a . must try them all. That is why the cost is O(26^d · L) for d wildcards, since each dot multiplies the branching. A query of all dots explores every path of the right length, which is worth stating when the interviewer asks about complexity. With no dots the search is a single O(L) walk.
3. The labels need not be characters
For a filesystem, split the path and use the components:
def resolve(root, path):
node = root
for part in path.split('/'):
if part: # skip the empty leading segment
node = node.children.setdefault(part, Node())
return node
mkdir is resolve and stop. addContentToFile is resolve then append to that node's content. ls is: resolve, and if the node is a file return its own name, otherwise return its children's names sorted. The whole API is three lines of trie walking plus that one branch.
4. A 30-second worked example
Insert cat, car, card; then query c.r:
Three words, five nodes below the root: the shared prefix ca is stored once. And note search("ca") returns False despite that path existing, because no key ends there.
5. Where you'll actually meet this
- Autocomplete. Each keystroke descends one node; the subtree below is the candidate set.
- Pattern lookups with blanks. Crossword and word-game helpers match patterns like
.a.e, which is the.branch. - Filesystems and object stores. Path hierarchies, and prefix-based listing APIs.
6. Problems in this chapter
Add and Search Word
Support adding words and searching with . matching any single character. Exact characters descend; wildcards branch to every child.
Pattern: trie with DFS on wildcards. Target: O(L) add, O(26^d · L) search.
Design In-Memory File System
Implement ls, mkdir, addContentToFile and readContentFromFile. A trie over path components, where files carry content and directories carry children.
Pattern: trie with non-character labels. Target: O(D) per operation for a path of D components, plus O(c log c) to sort the c children in ls.
Longest Word in Dictionary
Find the longest word in a list whose every prefix is also in the list, smallest alphabetically on ties. Insert everything, then walk the trie only through nodes marked as complete words.
Pattern: trie walk restricted to is_end nodes. Target: O(L) for L total characters.
7. Common pitfalls
- Omitting
is_end. Every prefix of a stored word would report as present. - Treating a wildcard as a single wrong guess. It must try every child, which means recursion rather than iteration.
- Not handling the empty path segment. Splitting
"/a/b"yields a leading empty string that must be skipped. - Returning unsorted
lsoutput. The problem requires lexicographic order; decide whether to sort on write or on read. - Confusing a file with a directory.
lson a file returns the file's own name, not its (nonexistent) children. - A 26-slot array for path components. Fine for lowercase letters, useless for arbitrary names, so use a dictionary.
- Recursing per character on a very long word. Deep tries can exhaust the stack; iterate for exact search and recurse only for wildcards.
- Descending through non-words. In Longest Word in Dictionary, only nodes with
is_endset may be walked through; skipping that check accepts words with a missing prefix.
8. Key takeaways
- A node is children plus an end-flag. The flag is what makes membership different from prefix existence.
- Exact search narrows; wildcards branch. That difference is the whole cost model.
- Labels can be anything: characters, path components, bits.
- A filesystem is a trie, and recognising that turns a design question into a walk.
- Sorted listing is a stated requirement, so choose where to pay for it.
- Dictionaries beat fixed arrays for anything but a small known alphabet.
- Why interviewers like it: the structure takes five minutes, leaving the whole interview for the extensions: wildcards, deletion, sorted listing, memory trade-offs.
Order: Add and Search Word (Wildcard) → Design In-Memory File System → Longest Word in Dictionary.
Longest Word in Dictionary
Core idea: A word is "buildable" only if you can grow it one letter at a time and every intermediate stub is also a real word in the list:
a,ap,app,appl,apple. Insert all words into a trie, then walk down only those branches where every step is the end of a word. The deepest node you reach spells the longest buildable word. Explore children in alphabetical order and ties go to the lexicographically smallest with no extra work.
Problem, rephrased
A release platform rolls feature flags out incrementally: a flag may go live only when its parent (the flag one character shorter) is already live, chaining all the way down to a single-character root. You're given an array words of lowercase strings: the flags that currently exist.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson