Tries: The Prefix Tree

Trees, Heaps and Tries · 30 min

Data structures & algorithms · Strings

Tries: the prefix tree

CAT, CAR and CARD are ten characters, and one trie stores them in five nodes below a single shared root. Build it here a character at a time and see exactly where the sharing stops and the branch begins.

Build the trie one character at a time →
CAT + CAR + CARD · 10 characters
→
one trie · 5 nodes below the root

01 The idea

One node per distinct prefix

A search box suggests words before you finish typing them. It cannot afford to look at every word in its dictionary on every keystroke. It needs a structure where the letters you have typed so far are not a string to compare against, but a place you can stand on.

A trie is that structure. Start at an empty root. To store a word, walk down one character at a time, following the child for that character if it exists and creating that child if it does not. The word CAT becomes a path of three nodes, and each node you land on along the way spells one prefix of it: C, then CA, then CAT. The name is short for retrieval, and most people say it like "try".

Walk the word one character at a time from the root. Follow the child for that character if it already exists; create it only when it does not. Mark the last node as the end of a word. Two words that start the same share every node up to the point where they differ.
NodeA map from a character to a child node, plus one flag. It stores no character of its own — the character is the key its parent used to reach it.
End-of-word flagA boolean meaning a word finishes exactly here. You need it because a word can end in the middle of a longer word, so "is this a leaf" is not the test.
PrefixAny leading run of characters of a word. Every path from the root down to a node spells exactly one prefix, so every node is exactly one prefix.

02 Hand trace

CAT, CAR and CARD into an empty trie

Insert CAT, CAR, CARD in that order. Each box is one node, labelled with the character on the edge that reaches it. A rose box is a node that had to be created; a plain box is a node that was already there and got walked onto for free. Watch when the plain boxes start appearing.

startrootempty trie · one root node, no children
insert CATCATnothing existed yet · 3 new nodes
insert CARCARC and CA reused · 1 new node · CA now has 2 children
insert CARDCARDC, CA and CAR reused · 1 new node
resultCARDT10 characters in · 5 nodes below the root

Count what happened. Ten characters went in and five nodes came out — six objects in memory if you count the root, which spells the empty prefix and was there before any word arrived — because CAR reused C and CA, and CARD reused C, CA and CAR. That saving is not a trick you apply afterwards; it is the definition of the structure. A node is a prefix, and those three words have only five distinct prefixes between them: C, CA, CAR, CARD, CAT. The node for CA is where the trie branches — it gained a second child the moment R arrived, and everything above it stays shared by all three words. The last row also tells you what a trie cannot do: nowhere is the string "CAR" stored. A word exists only as a path.

03 Code

Insert, and the one line that separates search from startsWith

The trace is the algorithm. Insert is a loop over the characters with a single decision inside it, and both query methods are that same loop with the create step deleted.

insert(word):    node = root    for ch in word:        if ch not in node.children:            node.children[ch] = new Node()        node = node.children[ch]    node.isEnd = true

Line 4 is the entire space argument. The check runs once per character and only succeeds for characters that are genuinely new. Inserting CAR after CAT, it fails for C and for A, so line 5 never runs and no memory is allocated for them. That is how ten characters became five nodes below the root.

Line 7 is not optional. Marking the last node is what makes CAR a stored word rather than a path you happen to be able to walk. Leave it out and the trie still has exactly the right shape and answers every question wrong.

Naive · scan every word

words = ["CAT", "CAR", "CARD"] startsWith(p):    for w in words:          # all N, every call        if w[0 : len(p)] == p:            return true    return false              # O(N x L)

Trie · walk the prefix once

walk(s):                # shared by both queries    node = root    for ch in s:        node = node.children.get(ch)        if node == null: return null    return node search(w):     n = walk(w); return n != null and n.isEndstartsWith(p): return walk(p) != null

A hash set has nothing to walk. It stores each word as one opaque key, so there is no way to ask it about CA except by testing every key it holds — O(N × L) per call, where N is the size of your dictionary. The trie turns the same question into O(L), and here L is 2. You pay for that in space rather than time: the trie holds one node per distinct prefix, and every one of those nodes carries its own child map, up to Σ slots each, where Σ is the alphabet size — 26 here, and much larger the moment the keys are Unicode.

search and startsWith differ by one clause. Both call the same walk. startsWith is happy the moment the walk survives: the node exists, so something in the trie starts with that string. search goes one step further and reads isEnd on that node. On this trie walk("CA") returns a real node, so startsWith("CA") is true — but that node's isEnd is false, because nobody inserted CA, so search("CA") is false.

Counting is the same walk plus a number. Keep a counter on every node and increment it on each node you step onto during an insert. Then countWordsWithPrefix("CA") is one two-step walk and one read: 3, because CAT, CAR and CARD all passed through. The counter at CAR reads 2.

05 Cheat sheet

The numbers you will be asked for

L is the length of the string you passed in. N is the number of words already stored. Notice which one shows up in the trie rows and which one does not.

OperationCostWhy
insert(word)O(L)A constant number of map lookups per character — one to test, one to step; a new node only where the path is new.
search(word)O(L)The same walk, then one read of isEnd at the last node.
startsWith(prefix)O(L)The same walk again; isEnd is never read.
countWordsWithPrefix(prefix)O(L)Walk to the node, read a counter maintained during insert — the one extra line the insert above does not have yet.
List every word under a prefixO(L + output)Walk to the node, then DFS its subtree; output is the total length of the answers.
Any prefix question on a hash set of N wordsO(N × L)Keys are opaque blobs, so every single one has to be tested.
SpaceO(Σ × total characters)At most 1 + sum of word lengths nodes, and each node carries a child map. A fixed array costs Σ slots per node (Σ = alphabet size, 26 for a–z); a hash map per node drops it to O(total characters) and adds a hash to every step. Shared prefixes are the discount on the node count.
L, never NEvery trie bound is the length of the string you handed in. A trie holding a million words answers search("CAR") in three steps, exactly like a trie holding three.
A node is a prefixThe number of nodes below the root is the number of distinct non-empty prefixes across all your words, not the number of characters you typed. The root itself is the empty prefix. That one sentence answers most trie space questions.
Sorted for freeVisit each node's children in key order during a DFS and the words come out alphabetically. No sort call, no comparator.

06 Where & why

When a trie beats a hash set

A trie is not a faster hash set. Exact lookup is O(L) either way, and the trie spends more memory getting there. What you buy is that a prefix stops being a string you compare against and becomes a node you can stand on.

Reach for it when…

The problem says prefixAutocomplete, "how many words start with", longest common prefix, word search on a board. If the word prefix appears in the statement, a node is the answer.
The keys share their beginningsEnglish words, file paths, phone numbers grouped by area code, IP prefixes in a routing table. Shared beginnings are stored once, so the trie is usually smaller than you fear.
You want the results in orderWalking children in key order emits words alphabetically, so the trie doubles as a sorted container with no sorting step bolted on.
The keys are bits, not lettersStore each number as its 32 bits and every node has at most two children. That is how maximum XOR over a pair drops from O(n²) to O(32n).

Use something else when…

SituationBetter choiceWhy
You only ever ask "is this exact key stored?"Hash setBoth are O(L), but the set holds one entry per word instead of one node per distinct prefix, each carrying a child map of up to Σ slots.
The keys share almost nothing — UUIDs, hashes, random tokensHash setNearly every character forks a new node, so you pay the full space cost and get none of the sharing back.
Memory is tight, or the alphabet is Unicode-wideRadix tree, or a ternary search treeA radix tree collapses every single-child chain into one edge; a ternary search tree replaces the per-node map with three pointers.
You need numeric ordering or range queriesBalanced BST or a sorted arrayA trie orders keys as text, so "10" sorts before "9" and a range scan gives you nonsense.
In an interview the trigger word is prefix. When you hear autocomplete, common prefix, or "words starting with", say trie first and then say why: a hash set can tell you whether a word is present, but it has no way to tell you what comes next without touching every key it holds.

07 Interview questions

Say these out loud

The CA question — startsWith true, search false — is the one that separates people who have read about tries from people who have built one.

What is a trie?
A tree in which every path from the root spells a prefix, and every stored word is one such path with a flag on its last node. The characters live on the edges, not inside the nodes, so words that begin the same way share the same nodes until the point where they differ. It is also called a prefix tree; the name comes from retrieval.
What does a single trie node actually store?
Two things: a map from a character to a child node, and a boolean saying whether a word ends here. It does not store its own character — that character is the key its parent used to reach it. Many implementations add a third field, a counter of how many words pass through, which is what makes prefix counts O(L).
Why do you need an end-of-word flag? Is a leaf not enough?
Because a word can end in the middle of a longer word. In a trie holding CAT, CAR and CARD, the node for CAR has a D child, so it is not a leaf, yet CAR is a stored word. Without the flag you also could not tell CAR from CA, and CA was never inserted.
What are the time complexities of insert, search and startsWith?
All three are O(L), where L is the length of the string you passed in. Each character costs a constant number of map lookups and nothing else. The number of words already stored does not appear in the bound at all, and noticing that is the point of the question.
A hash set already gives O(L) lookup. Why build a trie?
For exact lookup you would not — the hash set is simpler and uses less memory. The trie wins the moment the question is about a prefix. A hash set stores each key as an opaque blob, so "how many words start with CA" forces it to test all N keys, O(N × L). In a trie, CA is one node you reach in two steps.
What is the difference between search and startsWith?
They run the identical walk. startsWith returns true if the walk did not fall off the trie; search does that and then also checks isEnd on the node it landed on. On CAT, CAR and CARD, startsWith("CA") is true and search("CA") is false.
How much memory does a trie use?
At most one node per character inserted, plus the root, so the node count is bounded by 1 + sum of word lengths — 11 in the worst case for CAT, CAR and CARD, and 6 in reality because of the sharing: the root plus the five distinct prefixes. The real cost is per node: a 26-slot pointer array is fast but wastes most slots, and a hash map per node is compact but adds a hash to every step.
How would you count how many words start with a given prefix?
Keep a counter on every node and increment it on each node you step onto during an insert. The count for a prefix is then one walk of length L and a single read. Doing it by running a DFS over the subtree instead is correct but costs the size of that subtree, which is exactly what the question is asking you to avoid.
How do you delete a word from a trie?
Walk to the last node and clear its isEnd flag; that alone is already a correct delete. To reclaim memory, recurse back up and free a child only when that child has an empty children map and isEnd false. Deleting CAR from CAT, CAR and CARD frees nothing, because the node for CAR still has D hanging off it.
How would you build an autocomplete on top of this?
Walk to the prefix node in O(L), then DFS its subtree, collecting characters on the way down and emitting a string every time you hit a node with isEnd set. Visiting children in sorted key order makes the results come out alphabetically for free. The cost is O(L) plus the total length of the answers, never the size of the dictionary.
What is a bit trie, and how does it find the maximum XOR of a pair?
A bit trie stores numbers instead of words: each number is inserted as its bits from the most significant down, so every node has at most two children, 0 and 1. To maximise a XOR b, insert everything, then for each a walk down preferring the opposite bit whenever that child exists, because a 1 in a higher bit outweighs every bit below it. That is O(32) per number, so O(32n) instead of O(n²).
What is a compressed trie or radix tree?
A trie in which any chain of nodes with a single child is collapsed into one edge labelled with the whole substring. For just CAT and CARD, a plain trie needs 5 nodes below the root; a radix tree needs 3 — "CA", then "T" and "RD". Same idea, far less pointer chasing, which is why IP routing tables and several key-value stores use this shape rather than a plain trie.

08 Practice problems

Six problems, one structure

Five of these are the same walk from the root, and what changes is the question you ask at the node you land on. The sixth changes which strings you hand to insert in the first place.

Build the trie

Easy
Implement a Trie class with insert(word), search(word) and startsWith(prefix) over lowercase letters, the last two returning booleans.
Follow-up
The empty string is a legal argument to both queries, and on a trie built from real words the two methods disagree about it, so decide what your walk hands back when the loop body never runs before you write either verdict.
Show the hint
Give the walk one job — consume the characters and return the node it is standing on, or nothing at all. With zero characters it is still standing somewhere.

Longest common prefix

Easy
Given a list of words, return the longest string that is a prefix of every one of them, or the empty string if there is none.
Follow-up
The answer is a path down from the root rather than a column-by-column comparison across the list, but two different things can end that path, and a solution that only watches for branching returns a prefix longer than the shortest word.
Show the hint
Trace the list CAR, CARD by hand: the descent has to stop at the node for CAR, and that node has something set on it that its parent does not.

Replace words with their roots

Medium
Given a list of root words and a sentence, replace every word of the sentence with the shortest root that is a prefix of it, leave a word unchanged when no root is a prefix of it, and return the rebuilt sentence.
Follow-up
Two roots can both be prefixes of the same word — CAT and CATTLE both sit inside CATTLES — and the answer is the shorter one, so a walk that runs to the end of the word and then reports what it passed is doing more work than the problem allows.
Show the hint
You are asking a question at every node you land on, not only at the last one, and the first yes ends that word.

Longest word built one letter at a time

Medium
Given a list of words, return the longest word in the list that can be built one character at a time by other words in the list, breaking ties in favour of the alphabetically smallest.
Follow-up
It is not simply the longest word in the list: APPLE only counts if A, AP, APP and APPL were all inserted too, so the property you are testing lives on every node of the path, not just on the last one.
Show the hint
Descend from the root, and before stepping through a child ask that child the same question search asks at the end of its walk.

Longest shared prefix across two lists

Medium
Given two arrays of positive integers, write each number as its decimal digit string and return the length of the longest common prefix shared by any number of the first array with any number of the second, or 0 if none of them share a digit.
Follow-up
The answer is a length rather than a boolean, so the walk has to report how far it got before it fell off — and only one of the two arrays ever needs to become a trie, which is what stops the cost growing with the number of pairs.
Show the hint
Decide which array to insert; the other one only ever queries, and each query is a walk that counts its own steps.

Count the distinct substrings of a string

Hard
Given a string S of length n, return how many distinct substrings S contains, counting a substring that appears at two positions only once.
Follow-up
This lesson's one-line claim — a node below the root is exactly one distinct non-empty prefix — is the whole algorithm once you work out which set of strings to insert, and you never compare two substrings against each other. The catch is the size: that trie holds O(n²) nodes, which is why real systems switch to a suffix automaton or a suffix array as n grows.
Show the hint
Every substring of S is a prefix of one of the n strings you get by chopping characters off the front of S.