Trie-Backed Design · bigonotes

When the keys of a design are sequences (characters of a query, folders of a path) and the questions are about prefixes, a trie is the natural store. Each node is one step along a key, so "everything under this prefix" is one subtree. The design question is usually what extra data each node carries, and whether you pay for it when writing or when reading.

The idea#

A trie node is a children dict plus whatever payload the problem needs: a value for a file path, or the best sentences for an autocomplete prefix. Walking a key of length L costs $O(L)$ , whatever the number of stored keys.

This works because every key with the same prefix shares the same path from the root. So the node at the end of a prefix is the root of a subtree that holds exactly the keys you want, and its payload can summarize them.

That payload is where the design choice comes in. For ranked results, such as autocomplete suggestions, there are two designs:

	Read-optimized	Write-optimized
Each node stores	its current top-k `(-count, sentence)`	a plain set of sentences below it
On a new or repeated sentence	re-rank every node on the path	add to the sets, bump one counter
On a keystroke	return the node's list	look up every sentence's count, take top-k with a heap
Suits	search bars (people read far more than they add)	telemetry and logging (heavy ingest, rare queries)

Autocomplete is read-heavy: the delay between pressing a key and seeing suggestions is what users feel, so paying on write is the usual choice.

How to spot it#

These cues point to a trie-backed design.

"starts with", "prefix", "type one character at a time"
paths like /a/b/c where a parent must exist before a child
"list the contents of a directory", "move a folder"
"top 3 suggestions by frequency, ties alphabetical"

If the query is "contains this word anywhere", a trie is the wrong tool: that needs an inverted index (see the table below).

Template#

Here is the read-optimized autocomplete from the table above. Each node holds its top-k, and a cursor remembers the current node between keystrokes.

node: children dict, top list of (-count, sentence), best first
record(sentence):
    old = count[sentence] (0 if new); new = old + 1; count[sentence] = new
    node = root
    for each ch in sentence:
        node = child ch of node, created if missing
        remove (-old, sentence) from node.top    # never hold it twice
        add (-new, sentence); sort; keep the first k
type(ch):
    if ch ends the sentence: record(typed); reset typed and cursor; return
    append ch to typed
    cursor = child ch of cursor, or nothing    # O(1): no walk from root
    return the sentences in cursor.top, or empty if cursor is nothing

A keystroke is now $O(1)$ plus copying k results. Recording a sentence of length L costs $O(L \cdot k \log k)$ . Once the cursor falls off the trie, it stays off until the sentence ends, because no stored sentence has that prefix. Counts only grow, so a sentence cut from a node's top-k can only come back through its own update: trimming to k is safe.

Autocomplete is not full-text search#

The template works only because the query is a prefix. A trie answers "starts with". Finding "iPhone" in the middle of "I want to buy an iPhone" is a different problem.

	Trie	Inverted index
Answers	"starts with ..."	"contains ..."
Query shape	one character at a time	whole words, multi-word queries
Structure	nested nodes	`word -> [doc ids]` dict of lists

Paths: trie or flat dict#

Tries also fit file paths, the other cue from the list above. Split on / and walk one folder per node. Each call is $O(L)$ in the number of path parts. A flat path -> value dict also gives lookups, but folder operations show the difference.

	Trie	Flat dict
Lookup	$O(L)$ walk	$O(L)$ to hash the string
List a folder	read `children` directly	scan every stored path
Move or rename a folder	re-link one subtree	rewrite every path under it
Memory	a node object per folder	compact strings

Pitfalls#

These mistakes cause the most wrong answers.

Skipping the last node on update. Every node on the path, including the final one, must re-rank.
Adding the new rank without removing the old one. A sorted structure then holds the sentence twice.
Re-walking from the root on every keystroke. Keep the current node; reset it on #.
Creating missing parents silently. Read whether the problem wants a missing parent to fail or to be created.
Using a trie for "contains" search. That is an inverted index.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Implement Trie, then the autocomplete system.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Design Search Autocomplete System

The read-optimized design keeps a sorted structure of (-count, sentence) at every node. On #, remove the old (-old, sentence) and add (-new, sentence) at each node on the path, including the last one. Keep a pointer to the current node instead of re-walking from the root.

Hint: Design Search Autocomplete System: rank on read

The write-optimized design keeps one sentence -> count dict as the only source of truth, and each node a plain set of sentences. Recording is cheap, and the query ranks with heapq.nsmallest(3, ...) over (-count, sentence).

Hint: Design Search Autocomplete System: follow-ups

Cap each node's list (for example the top 100) so popular short prefixes don't hold every sentence. At global scale, store one ranked set per prefix in a shared store, such as a Redis sorted set (ZSET) under a key like prefix:i_lov. Search bar: pre-rank in the trie; logging or analytics: rank on read; many servers: a shared ranked store.

Hint: Design File System

Walk one folder per node. createPath fails if any parent is missing or the final name already exists; get returns the node's value or -1. Don't create missing parents.

Hint: Design File System: follow-ups

For deep, narrow trees, compress single-child chains into one node (a radix tree). For concurrent creates, use a lock per node: creating /a/b/c only locks /a/b, while read locks on ancestors stop them from being removed. For crash recovery, append each operation to a write-ahead log before applying it, and replay the log on restart.

Hint: Design In-Memory File System

This extends the file-system trie with file contents and ls, mkdir and append operations. The full design is in the File System LLD.

Hint: Implement Trie (Prefix Tree)

The payload is one flag per node: does a word end here? search needs that flag at the last node; startsWith only needs the walk to succeed. See Standard Trie.

Key takeaways#

A trie turns "everything with this prefix" into one subtree, at $O(L)$ per walk.
Decide where ranking happens: on write (fast reads, autocomplete) or on read (fast writes, telemetry).
Keep a cursor between keystrokes so each character is $O(1)$ .
A trie answers "starts with"; an inverted index answers "contains".
For file paths, a trie makes listing and moving folders cheap compared with a flat path map.

Core idea#

When keys are sequences and queries are about prefixes, use a trie. Everything under a prefix is one subtree. The design question is what each node carries, and whether you pay on write or on read.

Key points#

A node is a children dict plus a payload. Walking a key of length L costs $O(L)$ .
Read-optimized autocomplete: each node stores its top-k (-count, sentence). Recording re-ranks every node on the path, the last one included.
Write-optimized: one sentence -> count dict as the truth, a set of sentences per node, and heapq.nsmallest at query time.
Keep a cursor between keystrokes, so each character is $O(1)$ . Reset it on #.
Global scale: one Redis sorted set per prefix. Cap each node's list to bound memory.
File System: walk one folder per node. createPath fails if a parent is missing or the name exists.
Concurrent creates: a lock per node, not one global lock. Crash recovery: a write-ahead log.

Which structure#

Need	Use
Search bar, read-heavy	Rank on write (top-k per node)
Telemetry, heavy ingest	Rank on read with a heap
"Contains this word"	Inverted index, not a trie
List or move a folder	Trie, not a flat `path -> value` dict
Deep, narrow paths	Radix tree (compress single-child chains)

Template#

record(sentence):
    old = count[sentence] (0 if new); new = old + 1
    node = root
    for each ch in sentence:
        node = child ch of node, created if missing
        remove (-old, sentence) from node.top
        add (-new, sentence); sort; keep the first k
type(ch):
    cursor = child ch of cursor, or nothing    # O(1) per keystroke
    return cursor.top, or empty

Pitfalls#

Skipping the last node on update.
Adding the new rank without removing the old one. The sentence appears twice.
Re-walking from the root on every keystroke.
Creating missing parents silently in File System.
Using a trie for "contains" search.

Say it in an interview#

"Autocomplete is read-heavy, so each node pre-stores its top three."
"A trie answers starts-with. Contains needs an inverted index."