Pattern 5: Trie (prefix tree)

The Trie is a tree specialized in text: each edge is a character, and each path from the root downward spells a prefix. It makes "does this word exist?" and "does any word start with this prefix?" very efficient — and it is the basis of autocomplete.

🎯

Try it first: Implement Trie (Prefix Tree)

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Implement a Trie (prefix tree) with insert, search (exact word) and startsWith (prefix). For testing, you receive two lists: operacoes (e.g. "Trie", "insert", "search", "startsWith") and args (the argument of each operation). Return the list of results (None for build/insert, true/false for the searches).

Example: ops ["Trie","insert","search","search","startsWith"], args [[],["apple"],["apple"],["app"],["app"]] → [null,null,true,false,true].

Carregando editor…

Did you try? Storing the words in a list and searching one by one is O(n·m) per search. The theory below shows how the per-character tree structure makes each search proportional only to the length of the word.

The theory: paths that spell words

In a Trie, each node represents a prefix, and its children are the possible next characters. Words that share a prefix share the same path — hence the efficiency and the space savings.

inserting "casa", "caso", "cair":

        (root)
          │ c
          c
          │ a
          a
         / \
      s/   \i
      s     i
     / \     \
    a   o     r
   (casa)(caso)(cair)

Each node needs two things:

a map of children ({character: next node});
an end of word flag, marking that some path ends there (to distinguish a complete word from a mere prefix).

The three operations all walk letter by letter the same way:

insert(word):     walk, creating the missing nodes; mark the last as the end.
search(word):     walk; does the whole path exist AND is the last one the end?
startsWith(pref): walk; does the whole path exist? (it need not be an end)

The difference between search and startsWith is only the end flag — that flag is what separates "does the word cas exist?" from "is there a word that starts with cas?".

Carregando editor…

Why is the Trie efficient?

Each operation (insert/search/startsWith) walks one node per character of the word/prefix → O(L), where L is the length — regardless of how many words are already stored! Comparing against a list of words would be O(n·L) per search. The Trie's cost is space: nodes for each distinct character of the prefixes (mitigated by sharing common prefixes).

Where the Trie shines

Autocomplete, spell checking, prefix search, and problems that match many words at once against a text/grid (like Word Search II, which combines Trie

DFS on the grid from the Matrix section — Trie to check many prefixes at the same time). Whenever the problem is about prefixes or a dictionary of words, think Trie.

🧠 Review quiz

0/4

1. What does each node of a Trie represent, and what does it store?

2. What is the ONLY difference between search(word) and startsWith(prefix)?

3. Why is each Trie operation O(L) (L = length of the word)?

4. Why do words that share a prefix save space in a Trie?

Summary

Trie: a tree where each edge is a character; a path spells a prefix.
Each node: map of children + end of word flag (separates word from prefix).
insert/search/startsWith walk letter by letter: O(L), regardless of the number of words.
It shines at autocomplete, prefix search and matching many words (Word Search II).

Last stop: the synthesis of the Trees section and the quiz before the exam.

All lessons in this section