How a Phone Suggests the Next Word: Tries
Suggest words from a 100,000-word dictionary on every keypress, and learn new words as they're typed: why checking every word, a hash set and a sorted array each fall short, and the structure that fixes them, the trie.
Journeyman · Data Structures · Updated
After this lesson you can
- Trace how a trie stores words letter by letter, sharing common beginnings
- Find every word in a trie that starts with a given prefix
Key takeaways
- Checking every word is 100,000 checks per keypress, a hash set can't answer "what starts with car?", and a sorted array starts over on every key and slides to learn a word.
- A trie is a tree of letters: each node is one letter, and words with the same beginning share the same path from the root.
- Each node marks whether a word ends there, so car and card can both live on one path.
- Adding or finding a word takes one step per letter, however many words the trie holds.
- Every word that starts with a prefix sits under the prefix's node, so autocomplete walks down the prefix, then collects the words below it.
Before this: A hash set, from Module 5, answers "is this a word?" in one step, but not "which words start with car?".
Type "car" on your phone and the keyboard offers card, care and cart before you've finished thinking. Its dictionary holds 100,000 words, and it has two jobs:
- Suggest on every keypress. Type c, then a, then r: three keypresses, three new lists of words that start with what you've typed.
- Learn new words. A friend's name or a new slang word you type joins the dictionary, and gets suggested next time.
A search box does the same as you type a city or a product name. You'll build this for autocomplete, spell checkers, and any feature that asks "what starts with this?".
What would you try?
Check every word. After each keypress, ask every word in the dictionary whether it starts with what's been typed: 100,000 checks per key, O(n). Typing a seven-letter word is 700,000 checks, on a phone, while the person waits for the suggestions.
A hash set. Module 5's hash set answers "is card a word?" in O(1). But "which words start with car?" isn't a question about one word. The hash function scatters car, card, care and cart into unrelated buckets, so the only way to find them is to check every word: the first try again.
A sorted array, with binary search. This one is honestly good. In A to Z order, every word starting with "car" sits side by side, so binary search finds the first of them in about 17 looks, and reading along until a word stops starting with "car" collects the rest: O(log n + k), with k the words found. But each keypress starts a new search from the whole dictionary, even though the words starting with "car" are all inside the ones starting with "ca" that it found a moment ago. And learning a new word means sliding the words after it along to make room, about 50,000 slides each time.
| What we tried | Suggestions per keypress | Learn a new word | Where it breaks |
|---|---|---|---|
| Check every word | O(n): 100,000 checks | O(1) | every keypress |
| Hash set | can't answer "starts with" | O(1) | the question itself |
| Sorted array | O(log n + k): about 17 looks, then read along | O(n): about 50,000 slides | learning words, and starting over on every key |
The questions that lead to it
One more letter typed: must we start from the whole dictionary again? Every word that starts with "car" also starts with "ca". The answer to the new question is inside the answer to the last one.
What do car, card, care and cart have in common? Their first three letters. A dictionary stores those three letters over and over, once per word.
So what if words that start the same shared their start? Store c once, a under it once, r under that once, and hang d, e and t off the r. Then each keypress is one step down from where you already are, and everything below that spot starts with what's been typed.
How it got its name
This idea was so useful that it got a name: a trie (most people say it like "try"; it comes from retrieval). A trie is a tree where:
- the root stands for the empty beginning, before any letter;
- each node below it is one letter, and the path from the root to a node spells out a beginning, called a prefix: c, then ca, then car;
- a node is marked when a whole word ends there.
Words that start the same share the same path. Store cat, car and card, and the c and the a are stored once: the path splits after "ca" into t and r, and card keeps going one letter past car. Because car is a word on its own, its r node is marked as a word's end, even though the path continues to d.

Finding a word, and finding a beginning
To find out whether car is a word, start at the root and follow c, a, r. If a letter's node isn't there, the word isn't either. If you reach the last letter, check its mark: the path for "ca" exists, but no word ends at its a, so "ca" is a prefix, not a word.
That's three steps for a three-letter word, whether the trie holds ten words or ten million. The cost depends on the length of the word, not on how many words there are. And typing one more letter is one more step down from the node you're already on, not a new search of the whole dictionary.
To suggest words, an autocomplete walks down the prefix the user has typed, then collects every word in the subtree below that node: everything under "car" starts with "car", and nothing else does.
A trie in code
Each node keeps its children by letter (a dictionary from a letter to the next node) and a flag for "a word ends here". The trie adds six words, then checks two and suggests words for two prefixes. The suggestions are collected with a pre-order walk from Print the Chart, Count the Teams: Walking a Tree in the Right Order, visiting the letters in A to Z order, so the words come out alphabetized.
Trie words = new Trie();
foreach (string word in new string[] { "cat", "car", "card", "care", "cart", "dog" })
{
words.Add(word);
}
Console.WriteLine("Is car a word? " + (words.Contains("car") ? "yes" : "no"));
Console.WriteLine("Is ca a word? " + (words.Contains("ca") ? "yes" : "no"));
Console.WriteLine("Starting with car: " + string.Join(", ", words.StartingWith("car")));
Console.WriteLine("Starting with ca: " + string.Join(", ", words.StartingWith("ca")));
class TrieNode
{
public SortedDictionary<char, TrieNode> Children { get; } = new SortedDictionary<char, TrieNode>();
public bool EndsWord { get; set; }
}
class Trie
{
private readonly TrieNode root = new TrieNode();
public void Add(string word)
{
TrieNode current = root;
foreach (char letter in word)
{
if (!current.Children.ContainsKey(letter))
{
current.Children[letter] = new TrieNode();
}
current = current.Children[letter];
}
current.EndsWord = true;
}
public bool Contains(string word)
{
TrieNode? node = Find(word);
return node != null && node.EndsWord;
}
public List<string> StartingWith(string prefix)
{
List<string> found = new List<string>();
TrieNode? node = Find(prefix);
if (node != null)
{
Collect(node, prefix, found);
}
return found;
}
private TrieNode? Find(string letters)
{
TrieNode current = root;
foreach (char letter in letters)
{
if (!current.Children.TryGetValue(letter, out TrieNode? next))
{
return null;
}
current = next;
}
return current;
}
private void Collect(TrieNode node, string soFar, List<string> found)
{
if (node.EndsWord)
{
found.Add(soFar);
}
foreach (KeyValuePair<char, TrieNode> child in node.Children)
{
Collect(child.Value, soFar + child.Key, found);
}
}
}
Is car a word? yes
Is ca a word? no
Starting with car: car, card, care, cart
Starting with ca: car, card, care, cart, cat
class TrieNode {
TreeMap<Character, TrieNode> children = new TreeMap<>();
boolean endsWord;
}
class Trie {
private final TrieNode root = new TrieNode();
void add(String word) {
TrieNode current = root;
for (char letter : word.toCharArray()) {
current = current.children.computeIfAbsent(letter, key -> new TrieNode());
}
current.endsWord = true;
}
boolean contains(String word) {
TrieNode node = find(word);
return node != null && node.endsWord;
}
List<String> startingWith(String prefix) {
List<String> found = new ArrayList<>();
TrieNode node = find(prefix);
if (node != null) {
collect(node, prefix, found);
}
return found;
}
private TrieNode find(String letters) {
TrieNode current = root;
for (char letter : letters.toCharArray()) {
current = current.children.get(letter);
if (current == null) {
return null;
}
}
return current;
}
private void collect(TrieNode node, String soFar, List<String> found) {
if (node.endsWord) {
found.add(soFar);
}
for (Map.Entry<Character, TrieNode> child : node.children.entrySet()) {
collect(child.getValue(), soFar + child.getKey(), found);
}
}
}
void main() {
Trie words = new Trie();
for (String word : new String[] {"cat", "car", "card", "care", "cart", "dog"}) {
words.add(word);
}
IO.println("Is car a word? " + (words.contains("car") ? "yes" : "no"));
IO.println("Is ca a word? " + (words.contains("ca") ? "yes" : "no"));
IO.println("Starting with car: " + String.join(", ", words.startingWith("car")));
IO.println("Starting with ca: " + String.join(", ", words.startingWith("ca")));
}
Is car a word? yes
Is ca a word? no
Starting with car: car, card, care, cart
Starting with ca: car, card, care, cart, cat
class TrieNode:
def __init__(self):
self.children = {}
self.ends_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def add(self, word):
current = self.root
for letter in word:
if letter not in current.children:
current.children[letter] = TrieNode()
current = current.children[letter]
current.ends_word = True
def contains(self, word):
node = self._find(word)
return node is not None and node.ends_word
def starting_with(self, prefix):
found = []
node = self._find(prefix)
if node is not None:
self._collect(node, prefix, found)
return found
def _find(self, letters):
current = self.root
for letter in letters:
if letter not in current.children:
return None
current = current.children[letter]
return current
def _collect(self, node, so_far, found):
if node.ends_word:
found.append(so_far)
for letter in sorted(node.children):
self._collect(node.children[letter], so_far + letter, found)
words = Trie()
for word in ["cat", "car", "card", "care", "cart", "dog"]:
words.add(word)
print("Is car a word? " + ("yes" if words.contains("car") else "no"))
print("Is ca a word? " + ("yes" if words.contains("ca") else "no"))
print("Starting with car: " + ", ".join(words.starting_with("car")))
print("Starting with ca: " + ", ".join(words.starting_with("ca")))
Is car a word? yes
Is ca a word? no
Starting with car: car, card, care, cart
Starting with ca: car, card, care, cart, cat
class TrieNode {
constructor() {
this.children = new Map();
this.endsWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
add(word) {
let current = this.root;
for (const letter of word) {
if (!current.children.has(letter)) {
current.children.set(letter, new TrieNode());
}
current = current.children.get(letter);
}
current.endsWord = true;
}
contains(word) {
const node = this.#find(word);
return node !== null && node.endsWord;
}
startingWith(prefix) {
const found = [];
const node = this.#find(prefix);
if (node !== null) {
this.#collect(node, prefix, found);
}
return found;
}
#find(letters) {
let current = this.root;
for (const letter of letters) {
if (!current.children.has(letter)) {
return null;
}
current = current.children.get(letter);
}
return current;
}
#collect(node, soFar, found) {
if (node.endsWord) {
found.push(soFar);
}
for (const letter of [...node.children.keys()].sort()) {
this.#collect(node.children.get(letter), soFar + letter, found);
}
}
}
const words = new Trie();
for (const word of ["cat", "car", "card", "care", "cart", "dog"]) {
words.add(word);
}
console.log(`Is car a word? ${words.contains("car") ? "yes" : "no"}`);
console.log(`Is ca a word? ${words.contains("ca") ? "yes" : "no"}`);
console.log(`Starting with car: ${words.startingWith("car").join(", ")}`);
console.log(`Starting with ca: ${words.startingWith("ca").join(", ")}`);
Is car a word? yes
Is ca a word? no
Starting with car: car, card, care, cart
Starting with ca: car, card, care, cart, cat
class TrieNode {
children = new Map<string, TrieNode>();
endsWord = false;
}
class Trie {
private root = new TrieNode();
add(word: string): void {
let current = this.root;
for (const letter of word) {
let next = current.children.get(letter);
if (next === undefined) {
next = new TrieNode();
current.children.set(letter, next);
}
current = next;
}
current.endsWord = true;
}
contains(word: string): boolean {
const node = this.find(word);
return node !== null && node.endsWord;
}
startingWith(prefix: string): string[] {
const found: string[] = [];
const node = this.find(prefix);
if (node !== null) {
this.collect(node, prefix, found);
}
return found;
}
private find(letters: string): TrieNode | null {
let current = this.root;
for (const letter of letters) {
const next = current.children.get(letter);
if (next === undefined) {
return null;
}
current = next;
}
return current;
}
private collect(node: TrieNode, soFar: string, found: string[]): void {
if (node.endsWord) {
found.push(soFar);
}
for (const letter of [...node.children.keys()].sort()) {
this.collect(node.children.get(letter)!, soFar + letter, found);
}
}
}
const words = new Trie();
for (const word of ["cat", "car", "card", "care", "cart", "dog"]) {
words.add(word);
}
console.log(`Is car a word? ${words.contains("car") ? "yes" : "no"}`);
console.log(`Is ca a word? ${words.contains("ca") ? "yes" : "no"}`);
console.log(`Starting with car: ${words.startingWith("car").join(", ")}`);
console.log(`Starting with ca: ${words.startingWith("ca").join(", ")}`);
Is car a word? yes
Is ca a word? no
Starting with car: car, card, care, cart
Starting with ca: car, card, care, cart, cat
car comes before card because a node's own word is collected before the words below it, and cat comes after cart because, after "ca", r comes before t. To keep the letters in A to Z order, C# keeps each node's children in a SortedDictionary and Java in a TreeMap, the sorted maps from The Sorted Import That Made Search Crawl: Why Balance Matters; Python, JavaScript and TypeScript keep them in a dict or a Map and sort a node's few letters when they walk it.
Try it. Add the word "carpet" and ask for the words starting with "carp". Then ask for the words starting with "cow": the walk stops at o, which isn't under c, so the list is empty.
Where a real keyboard goes further
A phone doesn't show every word starting with "car"; it shows the three most likely. So each word's end can also hold how often it's used, and the keyboard picks the top three of the words it collected, with a heap from Who's Next in the Emergency Room? Heaps. A trie for finding the candidates and a heap for picking the best of them: that's how a suggestion box works.
The trie's cost card
Here L is the length of the word or prefix, and k the number of words that start with the prefix.
| Operation | Big-O | Why, in everyday terms |
|---|---|---|
| Add a word | O(L) | One step per letter, however many words are stored |
| Is this a word? | O(L) | Follow the letters, then check the mark |
| Every word starting with a prefix | O(L + the letters in the k words found) | Walk down the prefix, then visit only the words below it |
| Memory | Up to one node per letter stored | Shared beginnings are stored once; a big dictionary still takes many nodes |
When the sorted array wins
Be honest about the rival from What would you try?. For a fixed word list, such as a spell checker's dictionary that ships with the app and never changes, a sorted array with binary search is as good: O(log n + k) per question, far less memory (one string per word, not one node per letter), and simpler code. What tips the choice to a trie is the keyboard's other two needs: learning new words all the time, with no sliding, and answering each new keypress with one step from where it already is.
Check yourself
2 questions to try on the lesson page.
So what
When the question is "what starts with this?", a trie answers it by walking a few letters and collecting what's below. It's why your phone can suggest a word after one tap, out of a dictionary of hundreds of thousands.