vizlearn
Home / Algorithms

Trie (Prefix Tree)

Algorithms & Data StructuresBy Updated

Store words by their letters, sharing every common prefix. Lookup depends on word length, not dictionary size — which is why autocomplete stays instant no matter how many words you add.

Controls

Prefix Tree

step 0

Insight

Each edge is a character; each path from the root spells a prefix. Words sharing a prefix share the same nodes — stored once.

words0
nodes1
chars if stored flat0
saved by sharing0

Complexity

Search / insert O(L)
Autocomplete O(L + results)
Space O(total chars)

Overview

Searching for a word of length L costs O(L) — one step per character. Crucially, that is independent of how many words the trie contains. A dictionary of ten words and one of ten million both answer a five-letter query in five steps.

Lookup Does Not Care How Many Words You Have

Compare that with a balanced BST at O(L log n), where n is the dictionary size.

Prefix Queries Are the Real Superpower

A hash table can beat a trie for exact lookup — O(L) to hash versus O(L) to walk, with a smaller constant. But a hash table cannot answer "which words start with 'car'?" without scanning everything.

A trie answers it structurally: walk to the node for "car", then collect every word in the subtree beneath it. Press Autocomplete prefix and watch the subtree light up. That single property is why tries power search suggestions, IDE completion, and routing tables.

Marking Where Words End

Not every node is a word. Inserting "car" and "care" means "car" ends partway down the path to "care", so each node carries an is-word flag, drawn here as a filled circle.

Without it you could not tell whether a path spells a real word or merely a prefix of one — and searching for "ca" would wrongly succeed.

The Cost: Memory

Tries trade space for speed. A naive implementation gives every node an array of 26 child pointers, most of them null — enormously wasteful on sparse dictionaries.

Practical fixes: use a hash map of children instead of a fixed array, or switch to a radix tree (compressed trie), which merges chains of single-child nodes into one edge holding a whole substring. That is what IP routing tables use.

Watch the "saved by sharing" figure as you add words with common prefixes — sharing is what claws some of that memory back.

What it does that a hash table cannot

A hash set answers "is this exact string present?" in O(1). A trie answers several questions a hash set cannot answer at all.

QueryTrieHash set
Exact lookupO(m)O(1) average
Does any word start with this prefix?O(m)O(n) — scan everything
All words with this prefixO(m + output)O(n)
Longest prefix of this string that is a wordO(m)Not directly
Lexicographic iterationNaturalRequires sorting
Fuzzy match within edit distance kFeasibleNot directly

The prefix rows are the point. Autocomplete needs "all words starting with 'car'", and a trie walks three nodes and then collects the subtree. A hash set has no structure to exploit and must examine every key.

The longest-prefix match row matters in networking: IP routing tables answer "which routing rule has the longest matching prefix for this address?" and a trie over address bits does it in one pass. That is what a radix trie in a router is doing.

Space, and the two compressed variants

A naive trie is memory-hungry: one node per character per distinct prefix, and each node carries a dictionary. Storing a large English dictionary can use more memory than the strings themselves.

Two standard compressions:

Radix trie (Patricia trie) merges chains of single-child nodes into one edge labelled with a substring. A trie storing only "internationalisation" becomes two nodes rather than twenty-one. This is the variant used in routing tables and in some database indexes.

DAWG (directed acyclic word graph) also merges identical suffixes, so "running" and "jumping" share their "ing" ending. Far smaller, and it cannot store values per word, so it suits membership testing rather than mapping.

StructureSpaceSupports values
Standard trieLargestYes
Radix trieMuch smallerYes
DAWGSmallestNo

For most applications a standard trie with dictionary children is fine, and a radix trie is worth the extra complexity when the key set is large and shares long prefixes.

Things to try with Trie

  1. Load the sample words and note how car, card, care and careful all share one path for 'c-a-r'.
  2. Insert a word starting with a new letter. A whole new branch appears from the root — nothing to share.

Sources and next steps

Run it in Python

A trie built from a handful of words, with the node count printed against the character count so the sharing is visible. Then autocomplete, which is the operation a hash table cannot do at all.

trie.pyPython 3
Output
How the code works
  1. self.children = {}A dictionary per node rather than a fixed array of 26. It costs more per node and handles any alphabet, including Unicode — the array version is faster and quietly assumes lowercase ASCII.
  2. self.is_word = FalseThe flag is why "ca" is not a word even though the path exists, and why "do" is one even though "dog" continues past it. Without it a trie can only answer prefix questions.
  3. for ch in word: node = node.children[ch]Lookup walks one node per character, so it costs O(length) no matter how many words are stored. A hash table also gets O(1)-ish, but it must hash the whole string first — also O(length).
  4. trie.nodes vs sum(len(w))The saving is real but modest, and it comes entirely from shared prefixes. A trie over unrelated strings uses more memory than storing them in a set.
  5. def collect(node, so_far):Autocomplete is a DFS from the prefix node. This is the operation a hash table simply cannot perform — hashing destroys the relationship between "car" and "card".
Change one thing
  • Insert "carpet" and re-print the node count. It adds three nodes, not six — car was already there.
  • Insert a hundred unrelated random strings and compare trie.nodes with the character count. The saving vanishes.
  • Add delete. The awkward part is knowing when a node may be removed: only when it ends no word and has no children.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: press Search word. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. What does the is_word flag distinguish?
  2. Trie lookup costs O(length of the word) because:
  3. The operation a hash table cannot do at all is:





 Cheat sheet
Trie (Prefix Tree)
Store strings as paths through a tree so words sharing a prefix share those nodes, making autocomplete an O(L) walk.
ALGORITHMS · vizlearn.in/dsa/trie_prefix_tree.html
More in Algorithms
AlgorithmsUnion-Find (Disjoint Set)AlgorithmsGraph RepresentationsAlgorithmsBreadth First SearchAlgorithmsDepth First Search
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact