Trie for prefix queries

45 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You keep a list of words: apple, app, ape. People ask two kinds of question: "is app a word?" and "does any word start with ap?" By hand, with a short list, you read down the list and compare. With a dictionary of 100,000 words, answering "any word starting with ap" means comparing the prefix against every entry, and each comparison can take several letters: around 100,000 × (prefix length) steps per question. Sorting the list helps the first question but the prefix question still needs a search plus a scan.

Build the structure, one piece at a time

Instead of storing words whole, store them letter by letter along shared paths. Start with a single empty node, the root. A node has up to 26 children, one per letter, and a flag that says "a word ends here".

1. Insert apple: the root has no child a, so create one. That node has no child p, create it. Continue for p, l, e, creating five nodes in a line. Mark the last node (e) as a word end.
   Levels: root → a → p → p → l → e✓
2. Insert app: walk a, p, p; all three nodes already exist, nothing is created. Mark the second p as a word end.
   Levels: root → a → p → p✓ → l → e✓
3. Insert ape: a and p exist; e does not exist under that p, so a new branch starts.
   Levels: root → a → p → { p✓ → l → e✓ , e✓ }

Now the questions become walks. search("app"): walk a, p, p, arrive at a node with the flag set: true. startsWith("ap"): walk a, p, the path exists, no flag needed: true. search("apl"): after a, p there is no child l: false. This tree of letters is a trie (from "retrieval").

Why it is correct

The invariant: a word is in the set exactly when the path spelling it, letter by letter from the root, exists and ends at a flagged node. Insert creates exactly that path and sets exactly that flag, and never removes anything, so inserting one word cannot make another disappear. Two words that share a prefix share the nodes of that prefix, which is why app and apple coexist: the flag, not the end of a path, says where a word stops. A prefix query asks only whether the path exists, which is true exactly when some inserted word begins with it.

search(w) = path(w) exists and flag(end of path) ; startsWith(p) = path(p) exists

Why it is fast

Every operation walks one node per letter, and moving to a child is an array lookup or a hash lookup, constant time. So insert, search and prefix check each cost O(L) for a word of length L, no matter how many words are stored: 100,000 words or 10 million, startsWith("ap") is two steps. Memory is at most one node per letter of every inserted word, often far less because of shared prefixes.

How to recognise it in an interview

Cues: many strings, repeated questions about prefixes, autocomplete, "starts with", wildcard letters, or walking a grid while matching many words at once. Say: I will store the words in a trie so each query walks one letter at a time. Implement Trie (Prefix Tree) is exactly the structure above. Design Add and Search Words Data Structure adds a wildcard: at a . try every child. Search Suggestions System walks the typed prefix and collects the first three words below that node.

02The idea in one line

A tree of characters; a path spells a word, a flag marks word ends.

Reach for it when: Implement trie, add and search with wildcards, autocomplete, replace words.

Cost: O(L) per op.

03The walk-through, step by step

The video works one example: Insert 'apple', 'app'; search 'app'; startsWith 'ap'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Start with an empty root
2. insert 'apple': no child 'a', create it
3. insert 'apple': no child 'p', create it
4. insert 'apple': no child 'p', create it
5. insert 'apple': no child 'l', create it
6. insert 'apple': no child 'e', create it
7. End of 'apple': mark node 'e' as a word end
8. insert 'app': a → p → p already exist, just walk them
9. Mark the second 'p' as a word end too: the path is shared
10. insert 'ape': a, p exist; 'e' is a new branch under p
11. search('app'): walk a, p, p and the node has ✓ → true
12. startsWith('ap'): the path exists, no ✓ needed → true
13. search('apl'): after a, p there is no child 'l' → false
14. Every operation walks one character per step: O(L)

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Trie: Trie-guided grid DFS, Binary trie for maximum XOR.