Trie & Autocomplete

Type “te” into a search box and it offers tea, ted and ten before you finish. A trie stores words by their shared prefixes, so a lookup costs the length of the word, not the size of the dictionary.

intermediate⏱ 10 min read

←Builds on

5Trees: Concepts, Properties, TraversalsA trie is a rooted tree where every edge carries one letter.1Hash Tables: Sets & MapsThe children of a trie node are often kept in a map from letter to child.

Leads to→

11Prefix Function & KMPThe prefix function acts like failure links in a trie of the pattern: on a mismatch, fall back to the longest border.+Suffix ArrayA suffix array is the compact replacement for a trie of all suffixes.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01One letter per edge

A trie (prefix tree) is a tree in which every edge carries one character, so every path from the root spells a prefix. Words that start the same way share the beginning of their path: tea, ted and ten all go through t → e and split only at the last letter.

The root is empty. Each node keeps its children, one per possible next letter (an array of 26 for lowercase English, or a map), plus a flag end meaning “a whole word ends here”. The flag is essential: in and inn share the path i → n → n, and only the flags say that in and inn are words while i is not.

Building costs O(total length of all words): each insertion walks down letter by letter and creates nodes only where the path does not exist yet.

02Insert and search

Both operations start at the root and handle one character per step:

insert(word): for each letter, follow the child if it exists, otherwise create it; at the end set end = true.
search(word): follow the children; if a letter has no child, the word is absent and you stop at once. If you reach the end of the word, the answer is that node’s end flag.

So there are three outcomes. ten reaches a node marked end: a word. te reaches a node that is not marked: only a prefix. tx stops at the first missing child.

The cost is O(L) for a word of length L, however many words are stored. A hash set also checks membership fast, but it cannot answer questions about prefixes, and that is where the trie earns its memory.

03Dictionary, autocomplete, prefix counting

Store one more number in each node: cnt, how many inserted words pass through it (increment it on the way down during insert). Now the trie answers three classic questions:

Dictionary: is this a word? Walk down and check end: O(L).
Prefix counting: how many words start with p? Walk to p’s node and read cnt: O(|p|). For te the answer is 3.
Autocomplete: which words start with p? Walk to p’s node, run a DFS below it and output every node marked end. Visit the children in alphabetical order and the suggestions come out sorted: tea, ted, ten.

Real autocomplete also stores a popularity score and returns only the top few, but the skeleton is the same: walk down, then explore. Tries also power spell checkers, IP routing tables (longest prefix match) and, with bits instead of letters, the classic “maximum XOR of two numbers” trick.

Small badges: how many words pass through each node.

04Memory, and when to use a trie

The price of a trie is memory. With a 26-pointer array in each node, a dictionary of a million short words can need tens of millions of pointers, most of them NULL. Common fixes:

keep children in a map or a small sorted vector instead of a fixed array: less memory, slightly slower steps;
keep all nodes in one big array and use integer indices instead of pointers, int nxt[MAXN][26], the usual layout in competitive programming;
compress chains of single children into one edge labelled with a whole string (a radix tree).

Use a trie when the questions are about prefixes: autocomplete, counting words with a given prefix, the longest common prefix, replacing words by their shortest root. For a plain “is x in the set?”, a hash set is simpler.

Cost at a glance

Insert / search a word of length LO(L)

Count words with prefix pO(|p|)

Autocomplete prefix pO(|p| + subtree)

Memory (array children)O(total length · Σ)

Remember

A trie shares common prefixes: one edge per character and a flag in every node that marks the end of a word.
Insert, search and prefix counting all cost O(length of the string), independent of how many words are stored.
Autocomplete = walk to the prefix node, then DFS below it and collect every node that ends a word.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the small counters: each is the number of words passing through that node. At the end the trie autocompletes the prefix you choose.

Interactive visualizerfocus here, then space ← →

Trie (prefix tree)

end of a wordsmall number = how many words pass through this node

A trie stores strings by their characters: shared prefixes share nodes. We insert tea, ted, ten, to, in, inn.

Pseudocode

 1 root is empty; each edge is labelled by a character 2 insert(word): for each char, 3   follow the child if it exists, 4   else create a new child node 5   mark the final node as end-of-word 6 search(word): walk the same way, 7   hit only if the path exists AND the last node is end-of-word 8 // applications: dictionary, autocomplete, prefix count 9 autocomplete(p): walk to the node of prefix p10   DFS below it, collect every end-of-word node11 countPrefix(p) = cnt[node of p]   // O(|p|)

1 / 1

Check

Three questions. Pick an answer to see why.

The trie holds tea, ted, ten, to, in, inn. What does search("te") return?

How many nodes, not counting the root, does the trie of tea, ted, ten, to, in, inn have?

Which question does a trie answer quickly while a hash set cannot?

Practice

Real problems to lock it in, easiest first.

LeetCodeLongest Common Prefix beginner↗LeetCodeImplement Trie (Prefix Tree) intermediate↗LeetCodeSearch Suggestions System intermediate↗LeetCodeReplace Words intermediate↗LeetCodeMaximum XOR of Two Numbers in an Array intermediate↗