cf.completefrontend
TREES & TRIES · CORE

Trie (prefix tree)

Store words letter by letter in a tree so that all words sharing a start share the same path, which makes prefix lookups fast.

Time O(L) per insert or lookupSpace O(total letters)8 practice problemsStep-through picture

The idea

A trie (said like "try") is a tree for storing words. The root stands for the empty start. Each edge going down is one letter, so the path from the root to a node spells a prefix, the beginning of some word. Words that start the same way, like car, cart, and cat, share the same first nodes.

Each node keeps its children in a map from a letter to the next node, plus a flag isWord that says whether a stored word ends exactly here. The flag is needed because car can be a word while also being the start of cart.

To check a word or a prefix, follow its letters from the root. If a letter has no child, nothing stored starts that way. The cost depends only on the length of what you type, not on how many words are stored.

An everyday example

A phone's contact list grouped by letters

Picture a filing cabinet for names. The top drawer has one folder per first letter. Inside the "C" folder there is one folder per second letter, and so on. To find everyone starting with "Ca", you open "C" and then "a", and everything inside is your answer. A sticker on a folder marks that a full name ends there, like "Cal" inside the path to "Calvin".

How the example maps to the code
In the exampleIn the code
The top drawerroot, made with createNode()
A folder for the next letternode.children.get(ch)
Adding a missing foldernode.children.set(ch, createNode())
The sticker "a name ends here"node.isWord = true
Opening folders letter by letterfor (const ch of prefix)

From the slow way to trie (prefix tree)

  1. Autocomplete: the user types ma and you want every stored word that starts with it. The simple way loops over all n words and calls word.startsWith(prefix), which costs O(n · L) per keystroke for words of length L. With 100,000 words, every keystroke rereads them all.
  2. Words that share a start repeat the same letters: map, mat, and ma all begin with m, a. If those shared letters were stored once, a prefix question could follow them once and then look only at the words that really continue that way.
  3. So build a tree where each edge is one letter. A word becomes a path from the root, and words with a shared start share the top of the path. Each node needs a map from a letter to a child, plus a flag isWord, because a path can end at a real word, like ma, or only pass through on the way to longer words.
  4. Inserting follows existing edges and creates nodes only where a word goes somewhere new. Looking up a prefix follows its letters and stops at the first missing one. Each costs one step per letter, whatever the number of stored words. That tree of letter edges is a trie.

How it works

  1. Make an empty root node with createNode(): an empty children map and isWord: false.
  2. To insert a word, start at root and take its letters one by one.
  3. If the current node has no child for the letter ch, create one. Then move to that child.
  4. After the last letter, set node.isWord = true to mark that a word ends here.
  5. To look up a prefix, follow its letters from root. If a child is missing, return null.
  6. If every letter is found, return the final node. It exists means some word starts with prefix; its isWord says whether prefix is itself a stored word.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function createNode() {
  2. return { children: new Map(), isWord: false };
  3. }
  5. function insertWord(root, word) {
  6. let node = root;
  7. for (const ch of word) {
  8. if (!node.children.has(ch)) {
  9. node.children.set(ch, createNode());
  10. }
  11. node = node.children.get(ch);
  12. }
  13. node.isWord = true;
  14. }
  16. function findNode(root, prefix) {
  17. let node = root;
  18. for (const ch of prefix) {
  19. node = node.children.get(ch);
  20. if (node === undefined) return null;
  21. }
  22. return node;
  23. }

How fast it is

TimeO(L) per insert or lookup
Extra memoryO(total letters)

Each operation does one map step per letter of its word. Each new letter of a new word adds one node, so memory is at most the total length of all inserted words.

  • Best caseO(1)

    The first letter of the prefix has no child, as when looking up zebra in a trie with no z words: one map check.

  • Average caseO(L)

    A typical insert or lookup follows all L letters of its word, one Map step each.

  • Worst caseO(L)

    A word that's stored in full, or a long new word: every letter is one step. The number of stored words never matters.

Common mistakes

  • Forgetting the isWord flag and treating every node at the end of a path as a word. Then ca looks like a word just because car was inserted.
  • Checking only isWord for a prefix search. A prefix only needs the node to exist.
  • Building suggestions by scanning the whole word list again. Find the prefix node once and walk only below it.
  • Using a plain object for children with keys like constructor or __proto__. Use a Map or Object.create(null) to avoid clashes with built-in properties.

When to use it

Look for these clues in a problem:

  • The question is about prefixes: autocomplete, "starts with", or suggestions while typing.
  • You check many words against one dictionary, or one text against many words.
  • You need the shortest or longest stored word that is a prefix of something.
  • Words or paths share beginnings, like URLs split into segments or file paths split into folders.

Check yourself

Answer each one in your head first, then open it.

Why does a node need isWord when the node already exists?

A node can exist only because a longer word passes through it. isWord separates "a stored word ends here" from "some stored word continues past here".

In the trace, how many nodes did inserting ma create?

None. Both letters already had nodes from map, so the insert only set isWord on the a node.

Does lookup get slower as you add more words?

No. It takes one map step per letter of the prefix. More words add nodes elsewhere, but the path for one prefix stays the same length.

When is a sorted array better than a trie?

When the word list doesn't change and memory matters. Binary search finds the first match in O(L log n), and the array has no per-node overhead.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The property every insert keeps: each node stands for one prefix, the letters on the path from the root to it, and each prefix of a stored word has exactly one node. A node's isWord is true exactly when that prefix was inserted as a whole word. An empty trie has only the root, for the empty prefix, so the property holds.

Insert keeps it because it walks the word's letters from the root and creates a child only when the next letter has none. So the node for each prefix is reused if it exists and created once if it doesn't, never duplicated. The last node reached stands for the word itself, so setting isWord there marks exactly that word.

Lookup is then correct: a prefix has a node exactly when some stored word starts with it, and findNode reaches that node by following the same letters. If a letter is missing, no stored word has that prefix, so null is the right answer. Both loops run once per letter, so both end after L steps.

Going deeper

3 more ideas

Why shared starts are stored once

Inserting follows existing children as long as they match and only creates nodes where the word goes somewhere new. So car, cart, and cat share the nodes for c and a, and the trie stores each common start once. All words below a node share that node's prefix, which is why a prefix search can stop at one node and look only below it.

Listing suggestions

For autocomplete, find the node for what the user typed, then walk depth-first below it, adding letters to a string. Each node with isWord set is a suggestion. Visiting children in alphabetical order gives suggestions in alphabetical order, and you can stop after the first few.

Time and memory

Insert and lookup take O(L) for a word of length L, whatever the number of stored words. Memory is one node per distinct prefix, at most the total number of letters of all words. Maps make each node flexible; for only lowercase letters, an array of 26 slots is a common faster choice.

Work it by hand

Every step in a table, with why

Insert map, mat, and ma, then look up ma and me. The third word is a prefix of the first two, so it creates no nodes at all.

insertWord for "map", "mat", "ma"; then findNode(root, "ma") and findNode(root, "me")

StepCallchChild for ch?Nodes madeWhat happensWhy
1insert mapmmissing1create, step downThe trie is empty, so the root has no child for m. Line 9 creates one.
2insert mapamissing2create, step downThe new m node has no children yet, so a is created too.
3insert mappmissing3create, mark isWordAfter the last letter, line 13 marks the p node as the end of a word.
4insert matmexists3reuse, step downm already exists, so nothing is created.
5insert mataexists3reuse, step downa is shared with map as well.
6insert mattmissing4create, mark isWordOnly t is new. map and mat now share two nodes.
7insert mamexists4reuse, step downEvery letter of ma is already on a path.
8insert maaexists4reuse, mark isWordNo node is created. The a node existed only as part of longer words; now its isWord becomes true.
9find mamexists4step downLookup follows the same letters from the root.
10find maaexists4return the a nodeThe whole prefix was followed. The returned node has isWord = true and the children p and t.
11find memexists4step downThe first letter matches.
12find meemissing4return nullget("e") returns undefined, so line 20 returns null: no stored word starts with me.

3 words with 8 letters in total are stored in 4 nodes plus the root. findNode(root, "ma") returns a node with isWord = true, so ma is a word and also a prefix of map and mat. findNode(root, "me") returns null after 2 steps.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Trie (prefix tree)O(L)O(n · L)Many prefix questions, like autocomplete on every keystroke.
Scan with startsWithO(n · L)O(1)A few hundred words, or a one-time question: no setup is needed.
Sorted array and binary searchO(L log n)O(n · L)The word list is fixed and memory matters. Binary search finds the first word >= prefix, then read forward while words still start with it.
Hash set of wordsO(L)O(n · L)You only check whole words, never prefixes.

Extra memory: At most one node per letter of all inserted words, which is O(total letters), and less when words share starts. Each Map has a fixed overhead, so a trie uses more memory than a plain array of strings.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Trie (prefix tree) and the other approaches, on a scale where each line up is 10 times more steps.
  • Trie (prefix tree), Hash set of words O(L)
  • Scan with startsWith O(n · L)
  • Sorted array and binary search O(L log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Trie (prefix tree)101,0001 million
Scan with startsWith1001 million1 trillion
Sorted array and binary search339,96620 million
Hash set of words101,0001 million

Inputs that need care

5 tricky inputs
The empty string ""
insertWord(root, "") marks the root itself as a word, and findNode(root, "") returns the root, since every word starts with the empty prefix. Decide whether to allow it.
Inserting the same word twice
The second insert creates nothing and sets isWord = true again. To count copies, store a number instead of a flag.
A word that is a prefix of another, like ma and map
Both live on one path, and only isWord tells them apart. That's why findNode returns the node and lets the caller check isWord.
Upper and lower case, like Map and map
They're different letters, so they get different paths. Lowercase words before inserting and before looking up if case shouldn't matter.
Characters outside a to z, like accented letters or emoji
for...of walks by whole characters, so an emoji is one step, and Map accepts any key. A version that uses 26-slot arrays with ch.charCodeAt(0) - 97 would break on them.

Variations and follow-ups

Twists interviewers add

Suggestions under a prefix

Find the prefix node, then do a DFS below it, adding letters to a string, and collect every node with isWord set. To return only a few suggestions, stop after k words, or keep a short list of the best words at each node.

Delete a word

Clear isWord at the word's last node, then walk back up removing nodes that have no children and don't end another word. A recursive delete that tells its parent "remove me" is the simplest way to write it.

Wildcard search

To match m.p, where . stands for any letter, follow real letters normally and try every child at a .. It's a DFS that branches only at the wildcards.

Compressed trie (radix tree)

Merge chains of single-child nodes into one edge labeled with a string, like ap. It needs far fewer nodes for long words. Some URL routers match paths this way.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "prefix", "starts with", "autocomplete", "word dictionary", or many words searched at once in a grid of letters.
  • Draw three words sharing a start before coding, and point at the node where one word ends inside another. That shows why isWord is needed.
  • State the cost in terms of the word length L, not n: "insert and lookup are O(L) however many words are stored".
  • Expect "how would you return the top 3 suggestions?". Find the prefix node, walk below it in alphabetical order, and stop after 3, or keep a ranked top-3 list at each node and update it on insert.

Where frontend code uses it

The same idea in real UI code
  • Search boxes and command palettes suggest completions for what you have typed so far. A trie finds every stored entry with that prefix without scanning the whole list.
  • Client-side routers match a URL segment by segment, and route tables are often stored as a tree of segments, so routes that share a start like /settings/ share a branch.
  • Code editors keep large sets of file paths and symbols. VS Code's source code includes a ternary search tree, a kind of trie, for looking up paths and keys by prefix.

Related algorithms