DevPath
Tracks

Tries (Prefix Trees)

A tree keyed by characters that makes prefix search, autocomplete and word lookup cost O(length of the word), independent of dictionary size.

intermediate40 min#trie#prefix-tree#autocomplete#strings

Prerequisites: Trees and Binary Search Trees, Hash Tables

Why it matters

Autocomplete, spell checkers, IP routing tables, and word games all ask the same question: "which stored strings start with this prefix?" A hash table answers "is this exact word present?" in O(L) for a word of length L, but it cannot list words by prefix without scanning everything. A trie (pronounced "try", from retrieval) is built for prefixes, and its lookup cost depends only on the length of the query, not on how many words are stored.

Intuition

Open a paper dictionary. You do not read from page one; you narrow down by first letter, then second letter, then third. A trie encodes that narrowing as a tree. Each edge is a character, each path from the root spells a prefix, and words that share a beginning share the same path, so the prefix is stored only once.

 root
  |-- c
  |   `-- a
  |       |-- r *      "car"
  |       |   |-- d *  "card"
  |       |   `-- e *  "care"
  |       `-- t *      "cat"
  `-- d -- o -- g *    "dog"

A star marks a node where a word ends. "car" is a word and also a prefix of "card" and "care", which is why the end marker is needed: the path alone cannot tell you whether "ca" was inserted.

cardetdogrootccacarcardcarecatddodog
The same trie, with each edge labeled by its character and each node named by the prefix spelled so far. Amber nodes end a word (the stars above). The nodes c and ca are only prefixes, and the words car, card and care share one path instead of storing the letters three times.

How it works

Each node holds a map from character to child node plus an end-of-word flag. In our code the flag is a special key "$" inside the same map, which keeps the node a single dictionary.

  • Insert: walk down the word, creating missing children, then mark the last node as a word end. O(L).

  • Contains: walk down; fail if any character is missing; succeed only if the final node is marked. O(L).

  • Starts with: same walk, but success needs only that the walk finished. O(L).

  • Autocomplete: walk to the prefix node, then run a depth-first search below it to collect every marked node. Cost is O(L) plus the size of the subtree you enumerate. Visiting children in sorted order returns suggestions alphabetically.

cardedogrootccacarcardcareddodog
Trie holding car, card, care and dog. We insert cat. Start at the root.
step 1 / 6

Inserting cat. Green is the current node, amber nodes end a word. The first two letters follow existing edges, and only the missing letter creates a node.

cardetdogrootccacarcardcarecatddodog
Three lookups on the trie from the code. Amber nodes end a word. First: contains of ca, starts_with of ca, contains of car, then starts_with of cb.
step 1 / 5

Searching a trie. Prefix check and exact lookup use the same walk. They differ only in the last test: did the walk finish, versus does the final node carry the end mark.

Children representation. A map per node (dict, Map) is flexible and memory-proportional to what you store. A fixed array of 26 slots gives O(1) child access for lowercase English but wastes space when nodes are sparse. A compressed trie (radix tree) merges chains of single-child nodes into one edge labeled with a substring, trading simplicity for memory.

Trade-offs. A trie can use much more memory than a hash set, since every node carries its own map. It shines when you need prefix queries, sorted enumeration, or longest-prefix matching (as in routing). For plain membership tests, a hash set is simpler and smaller.

OperationTimeNotes
Insert word of length LO(L)Independent of word count
Exact lookupO(L)Needs the end marker
Prefix checkO(L)Hash tables cannot do this
List all words under a prefixO(L + size of subtree)DFS below the prefix node
SpaceO(total characters)Worst case; shared prefixes save space

Code: insert, lookup, autocomplete

import json
 
def show(*xs):
    print(*(json.dumps(x, separators=(',', ':')) for x in xs))
 
class Trie:
    def __init__(self):
        self.root = {}  # each node: dict of char -> child; "$" marks end of word
 
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True
 
    def _walk(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return None
            node = node[ch]
        return node
 
    def contains(self, word):
        node = self._walk(word)
        return node is not None and "$" in node
 
    def starts_with(self, prefix):
        return self._walk(prefix) is not None
 
    def autocomplete(self, prefix):
        node = self._walk(prefix)
        out = []
        def dfs(n, path):
            if "$" in n:
                out.append(prefix + path)
            for ch in sorted(k for k in n if k != "$"):
                dfs(n[ch], path + ch)
        if node is not None:
            dfs(node, "")
        return out
 
t = Trie()
for w in ["car", "card", "care", "cat", "dog"]:
    t.insert(w)
show(t.contains("car"), t.contains("ca"), t.starts_with("ca"), t.starts_with("cb"))
show(t.autocomplete("car"))
show(t.autocomplete("x"))

Both versions print:

true false true false
["car","card","care"]
[]

The first line shows that "car" is a stored word, "ca" is not a word but is a valid prefix, and "cb" is not a prefix. The second line is the autocomplete for "car" (the word itself plus its extensions), and the third shows an unknown prefix returns an empty list.

Common pitfalls

  • Treating a prefix as a word: contains must check the end marker; starts_with must not.
  • Colliding the marker with real characters: if your alphabet can include the marker (for example the dollar sign), use a separate boolean field on a node object instead.
  • Memory blow-up: a node object with a 26-slot array per character is heavy for large dictionaries. Prefer maps, or compress the trie.
  • Recursion depth: very long words recurse deeply in the DFS. Use an explicit stack if words can be thousands of characters.
  • Case and Unicode: normalize case first. For non-ASCII text, decide whether nodes are code points, bytes, or grapheme clusters.

Practice

Implement a trie with insert, search, starts-with easy

Hint

Share one helper that walks a string and returns the node it ends on, or nothing.

Show solution

Write a walk(s) helper that returns the final node or null. search is walk(word) is not null and has the end marker; startsWith is just walk(prefix) is not null. Each is O(L).

Longest common prefix of many strings medium

Hint

Insert everything, then walk from the root while the path does not branch.

Show solution

Insert all strings. From the root, repeatedly move to the only child as long as the current node has exactly one child and is not a word end. The characters you collect are the longest common prefix. O(total characters). (Comparing against the first string character by character is just as good and uses no extra memory.)

Word search II hard

Hint

Searching a grid word by word repeats work. Search for all words at once.

Show solution

Insert all target words into a trie. Run a DFS from each grid cell, moving through the trie in step with the grid path, and stop a branch the moment the current path is not a trie prefix. When you reach a word-end node, record the word (and clear the mark to avoid duplicates). The trie prunes dead branches that a per-word search would explore repeatedly.

Count words with a given prefix medium

Hint

Store a small counter in each node as you insert.

Show solution

Add a pass_count to each node that increments every time an insert passes through it. After walking to the prefix node, its pass_count is the answer in O(L), with no subtree enumeration.

Interview questions

  1. Why use a trie instead of a hash set of words? Prefix queries, sorted enumeration, and longest-prefix matching without scanning every word.
  2. What does lookup cost? O(L) for a word of length L, regardless of how many words are stored.
  3. What is the downside? Memory: each node has its own child container, so tries can be much larger than a hash set unless compressed.
  4. What is a radix tree? A compressed trie where single-child chains are merged into one multi-character edge.
  5. How would you rank autocomplete suggestions? Store a frequency at each word-end node and collect the top k (a heap helps) under the prefix.

Interviewers look for: recognizing prefix-search problems quickly, using the end-of-word marker correctly, and discussing memory trade-offs versus a hash set.

Quick check

A trie holds 500,000 words. How many node steps does it take to check whether the 5-letter word 'apple' is stored?

Finished this lesson?

Further resources

Related lessons