Tries: Prefix Trees

Tries & Bit Manipulation, lesson 1 of 3

Tries: Prefix Trees

Store words letter by letter so every prefix question costs O(length of the word).

12 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

A Python set answers "is apple stored?" in O(L) time (hash the word). But ask "is there any word starting with app?" and a set has no idea: you must scan every word, O(N · L).

A trie (say "try", from retrieval) fixes that by storing words one letter per level, so words with a common prefix share the same path. Here are app, apple, apt and bat (★ marks "a word ends here"):

(root)
 ├─ a
 │  └─ p
 │     ├─ p ★
 │     │  └─ l
 │     │     └─ e ★
 │     └─ t ★
 └─ b
    └─ a
       └─ t ★

Each node is just two things: a dict of children (letter → node) and an end flag. Walking from the root and following one letter at a time answers any prefix question in O(L), no matter how many words are stored.

Example

A trie in 30 lines

search and starts_with share the same walk; the only difference is the final is_end check. Try t.search("appl") and t.starts_with("appl").

Quiz

How many nodes (not counting the root) does this create?

Costs. Insert, search and starts_with are all O(L) time. Memory is O(total characters inserted), usually less thanks to shared prefixes.

When a trie beats a set:

  • prefix queries ("any word starting with...?", "how many words start with...?")
  • autocomplete: walk to the prefix node, then collect every word below it
  • wildcard patterns like b.d (branch on the dot)
  • searching for many words at once, e.g. on a letter grid: one walk checks every word sharing a prefix

If you only ever ask "is this exact word stored?", a set is simpler and just as fast.

You don't even need a class: a node can be a plain dict of children with a special key such as "$" for the end flag. That version is short enough to write from memory in an interview.

Example

Autocomplete with nested dicts

setdefault(ch, {}) returns the child, creating it if missing: one line per letter. Visiting children in sorted order yields suggestions alphabetically.

Quiz

Which task does a trie handle better than a plain set of words?

Exercise

Count words by prefix

Build a PrefixCounter class:

  • insert(word) stores a word
  • count(prefix) returns how many inserted words start with prefix (count("") is the total)

Make count O(len(prefix)): keep a counter on each node that says how many words pass through it. Every call to insert counts, even for a duplicate.