Trie: Paths, Terminals, and Constrained Search

Reader guide and study workflow · Complete course map

Start with competing ways to answer a prefix question

Store the words stone, stop, and sun. Exact membership can be answered with a hash set. To answer “does any word begin with sto?”, a simple baseline scans all three words and compares their prefixes. For a static sorted dictionary, a lower-bound search is another reasonable solution. A trie becomes useful when repeated queries or constrained searches repeatedly inspect the same prefixes; it shares that work explicitly instead of making “strings” an automatic trigger for one data structure.

Draw one path for each word and merge their common initial edges. Reaching s→t→o tells us that a prefix exists. It does not prove that sto itself was inserted. Add a terminal marker only at the ends of stored words. If stop is later extended to stops, the stop marker must survive: a node can be both an answer and a place to continue. The representation follows from two different questions that a plain path cannot distinguish.

Derive the state from what one step consumes

For exact membership, state is the current trie node and the unread suffix. A letter consumes one edge. With a wildcard dot, the same step may choose several existing edges, so return the OR of their suffix results; failure in the first branch must not end the whole search. Acceptance still requires a terminal at exactly the requested length.

Board search adds a constraint the trie does not encode: a cell cannot be reused within one candidate path. Two searches can reach the same trie prefix using different board cells and have different legal continuations. State therefore includes the current cell and path-local used cells. Mark before exploring and restore afterward. A global visited set would discard valid alternate paths; no visited set would allow illegal repeated cells.

For shortest-root replacement, reaching the first terminal is already enough. For finding all board words, the same early return would miss longer words that extend it. The data structure is shared, but the acceptance and stopping contracts differ. The workshop below develops those choices; keep the supplementary drills for a later attempt without this introduction in view.

Prerequisites and readiness

Know byte-indexed strings, fixed-size child arrays, recursion, and backtracking restoration. The course trie uses lowercase ASCII letters, not arbitrary Unicode text; understand that a terminal marker is separate from node existence.

Reasoning workshop: one path, four stopping rules

Build a trie by hand

Insert cat, car, then care. The first two edges c->a are shared. At a, one branch reaches terminal t; another reaches terminal r, which also has child e marked terminal. The path ca exists but is not a word. The path car is both a word and a prefix of a longer word. Inserting car again changes no membership fact.

root
  c
    a
      t [end]
      r [end]
        e [end]

Each insertion step establishes: the current node represents the consumed prefix. Exact Search accepts only at a terminal after consuming all input. StartsWith accepts after the path exists, even without a terminal. The empty prefix is the root path. Use Constructor so that root is allocated; do not assume the zero-value wrapper has an initialized root.

A wildcard consumes exactly one edge

With words bad, dad, mad, pattern .ad branches from the root into existing children, then follows literal a and d. Pattern .. fails because after two edges none of those nodes is terminal. Pattern b... fails because it demands four characters. A dot is not a star and never consumes an arbitrary suffix.

The recursive contract is Search(node, i): does any terminal descendant match precisely pattern[i:]? The base case checks the terminal flag when i equals pattern length. A literal recurses into one child; a dot returns the OR of valid child searches. Read-only searching must not clear end flags or mutate the dictionary. Repeating the same query should give the same result.

Board search adds a second state dimension

Word Search II carries both a trie prefix and a set of cells already used by the current board path. On board a,b with words a and ab, discovering a records one answer but must retain the a->b continuation. Clearing the stored terminal word is safe duplicate suppression; deleting the entire prefix branch is not.

Before recursion, temporarily mark the current board cell. After recursion, restore the byte. Without restoration, a completed branch steals cells from later branches and starting positions. Without marking, one path can illegally reuse a cell. The output is a set of distinct words, but the board must be exactly restored on return. A trie improves pruning, not the exponential worst-case nature of constrained path search.

Shortest root replacement stops early by design

With dictionary c, cat, cattle, scanning cattle reaches terminal c first and must stop. Continuing to a longer terminal would turn shortest-prefix replacement into longest-prefix replacement. Dictionary insertion order is irrelevant because all roots share the same path structure.

The current API accepts lowercase words separated by single spaces. Fields and Join preserve that contract, but do not promise to preserve arbitrary repeated whitespace outside it. Distinguish a domain restriction from an implementation bug before changing observable behavior. Likewise, a 26-child array is a deliberate domain choice: subtracting 'a' from an arbitrary Unicode byte is not a Unicode tokenizer.

Reconstruction drill

For each operation, name what is carried, what is consumed, and what causes acceptance. Insert carries a node and creates missing edges; exact search consumes every letter and checks terminal; wildcard search may branch but consumes one position each time; board search additionally owns a reversible visited set; root replacement accepts the first terminal. These differences explain the code more precisely than the generic instruction “use a trie.”

Reconstruction lab and answer key

Implement Trie (Prefix Tree)

Insert "sea" and "seal", then search "se", "sea", and prefix "se". Now suppose exact Search("se") accidentally sets an end flag. Which later observation exposes the mutation?

Model answer

The results must be false, true, and true. Repeating Search("se") must still be false; if it becomes true, a read operation changed membership. The node for sea remains terminal even though it has child l. Queries traverse existing edges and never create children or terminal flags.

Design Add and Search Words Data Structure

After adding "axe" and "box", evaluate ".ox", "..", and "b...". If the first wildcard branch is the a-child and fails, what must the search do next?

Model answer

The results are true, false, false. The .ox search must continue to the b-child after the a branch fails, where ox completes box. A dot consumes one edge and the pattern must end at a terminal; neither a short prefix nor an extra unmatched position is accepted.

Word Search II

On a one-row board [a,b,a] with words ["a","ab","aba","abaa"], give the distinct outputs. Explain separately why a prefix terminal cannot stop exploration and why abaa is invalid.

Model answer

The output set is {a,ab,aba}. Finding a must continue because ab and aba extend it; recording a once can clear only its terminal output marker. abaa would require four cells, so it cannot be formed without reusing a cell. Marks belong to one search path and must be restored for the opposite starting a.

Replace Words

Roots are ["be","bee","sun"], sentence is "bees sunset bedroom". Derive the output without relying on insertion order. If the task instead demanded longest roots, which stopping rule would change?

Model answer

The output is "be sun be". Each word stops at its earliest terminal prefix, so bee is never preferred over be. Longest-root replacement would remember the most recent terminal and continue until the path ends; it could choose bee for bees. The representation can stay the same while the acceptance policy changes.

Problems in this module

• Implement Trie (Prefix Tree)
• Design Add and Search Words Data Structure
• Word Search II
• Replace Words

Interactive checkpoint

Open the Trie quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Supplementary drills and answer key

Trie Drills and Answer Key

These drills are designed to make the learner reason about tries without hiding behind code. They can be used as lesson checks, interview warmups, homework, or spaced repetition.

---

Section A — Recognition drills

For each scenario, choose the most natural tool: hash set, trie, sorting/binary search, graph search, or another structure.

1. Check whether a submitted username exists exactly.
2. Check whether any username starts with the typed prefix.
3. Return the first five lexicographic usernames under a typed prefix.
4. Find whether "needle" appears as a substring inside a long text.
5. Given a board and 50,000 dictionary words, find all words on the board.
6. Given numbers, find the pair with maximum XOR.
7. Given a sentence, replace every word by the shortest dictionary root.
8. Given static sorted product names, return suggestions after each typed character.
9. Given file-system paths, find all files under /home/user/docs.
10. Given API routes such as /users/:id/orders, match incoming paths.

Answers

1. Hash set.
2. Trie.
3. Trie or sorted array with binary search; trie is natural if dynamic.
4. Not a normal trie; use KMP, suffix array, suffix automaton, rolling hash, or search index.
5. Trie + grid backtracking.
6. Bitwise trie.
7. Trie.
8. Sorted array may be enough if static; trie if dynamic or prefix-heavy.
9. Trie over path segments or file-system tree.
10. Trie/radix tree over path segments.

---

Section B — Invariant drills

1. What prefix does the root represent?
2. After inserting "tea", what prefixes definitely exist as paths?
3. After inserting "tea", should Search("te") return true?
4. What does node.isWord == true mean?
5. What does node.children['x'] != nil mean?
6. Can two different nodes represent the same prefix in a normal trie?
7. Can one node represent two different prefixes?
8. If StartsWith("abc") is false, can Search("abcd") be true?
9. If Search("abc") is true, must StartsWith("abc") be true?
10. If StartsWith("abc") is true, must Search("abc") be true?

Answers

1. Empty prefix "".
2. "" at the root, then "t", "te", and "tea".
3. No, unless "te" was separately inserted.
4. The path prefix is a complete inserted word.
5. At least one inserted word has the current prefix plus x.
6. No.
7. No.
8. No.
9. Yes.
10. No.

---

Section C — Trace drills

Given insertions:

car
card
care
cat
dog

Answer:

1. Search("car")
2. Search("ca")
3. StartsWith("ca")
4. StartsWith("cow")
5. Search("care")
6. Search("cart")
7. How many children does the node for prefix "ca" have?
8. Which words are in the subtree under "car"?
9. Which nodes are terminal on the path c -> a -> r -> e?
10. If "car" is deleted, should "card" remain searchable?

Answers

1. true.
2. false.
3. true.
4. false.
5. true.
6. false.
7. Two: r and t.
8. car, card, care.
9. car and care.
10. Yes.

---

Section D — Wildcard drills

Stored words:

bad
dad
mad
map
mass

Queries:

1. Search("bad")
2. Search(".ad")
3. Search("b..")
4. Search("..")
5. Search("m..")
6. Search("ma.")
7. Search("ma..")
8. Search("....")
9. Search("p..")
10. Search("...")

Answers

1. true.
2. true.
3. true.
4. false; length mismatch.
5. true (mad or map).
6. true (mad or map).
7. true (mass).
8. true (mass).
9. false.
10. true.

---

Section E — Replace Words drills

Dictionary:

a
an
ant
bat
bath
cat

Sentence words:

1. animal
2. antelope
3. battery
4. bathroom
5. catalog
6. dog
7. an
8. anthem

Answers

1. a.
2. a because shortest root wins, even though an and ant also match.
3. bat.
4. bat, not bath, because shortest root wins.
5. cat.
6. unchanged dog.
7. a if dictionary includes a; shortest root wins.
8. a.

Discussion: If the desired behavior is “longest root wins,” that is a different problem. The trie walk would continue and remember the latest terminal instead of stopping at the first terminal.

---

Section F — Word Search II drills

Board:

a b
c d

Words:

ab
abc
abd
abdc
acdb
ad

Assume movement is up/down/left/right only and cells cannot be reused.

1. Is ab found?
2. Is abc found?
3. Is abd found?
4. Is abdc found?
5. Is acdb found?
6. Is ad found?
7. Why is abcd a useful negative check on this board?
8. Why is trie pruning useful here?

Answers

1. Yes: a -> b.
2. No: from b, cannot go to c diagonally.
3. Yes: a -> b -> d.
4. Yes: a -> b -> d -> c.
5. Yes: a -> c -> d -> b.
6. No: a and d are diagonal.
7. abcd fails because after a -> b, the next needed cell c is diagonal from b. Diagonal movement is not allowed.
8. If the current path is not a prefix of any target word, the DFS can stop instead of exploring all continuations.

---

Section G — Code reading drills

Drill 1

What is wrong here?

func (t *Trie) Search(word string) bool {
    return t.find(word) != nil
}

Answer: It treats any prefix path as a full word. It must check node.isWord.

Drill 2

What is wrong here?

func Constructor() Trie {
    return Trie{}
}

Answer: root is nil. Insert will panic unless it initializes root elsewhere.

Drill 3

What is wrong here?

for _, ch := range word {
    idx := ch - 'a'
    node = node.children[idx]
}

Answer: Go permits a rune (an integer type) as an array index; its not being int is not a compilation error. The real preconditions are lowercase ASCII and an existing child before continuing. Outside a-z, ch-'a' can be out of the 26-slot range, and a missing edge can make node nil. Use guarded byte indexing under the lowercase contract, or a rune-keyed map for a deliberately code-point-based variant.

Drill 4

What is wrong here in wildcard DFS?

if i == len(word) {
    return true
}

Answer: It allows prefixes to match. It must return node.isWord.

Drill 5

What is wrong here in board DFS?

board[r][c] = '#'
// explore
return

Answer: It does not restore the cell before returning, corrupting the board for other paths.

---

Section H — Design drills

1. You need duplicate word counts. Which field do you add?
2. You need to erase words safely. Which field helps you prune?
3. You need to output the matched word in board search. What should terminal nodes store?
4. You need to return top 3 suggestions fast for every prefix. What could each node cache?
5. You need route matching for /users/:id. What is the trie alphabet?
6. You need maximum XOR. What is the trie alphabet?
7. You need Unicode words. What should children look like?
8. You need preserve exact sentence whitespace in Replace Words. Should you use strings.Fields?
9. You need all words under a prefix. What operation follows the prefix walk?
10. You need memory efficiency for millions of sparse nodes. What alternatives should you consider?

Answers

1. countWord.
2. countPrefix or child reference counts.
3. The full word string or an ID into the word list.
4. A sorted/capped top-K list.
5. Path segments, not characters.
6. Bits {0,1}.
7. map[rune]*node or a Unicode-aware structure.
8. No; scan tokens and separators manually.
9. DFS over the subtree.
10. map children, compressed trie/radix tree, DAWG/FST, sorted arrays, or external search index depending on requirements.

---

Section I — Implementation challenges

These are small enough to code in one sitting.

1. Implement Trie with Insert, Search, StartsWith.
2. Add CountWordsEqualTo and CountWordsStartingWith.
3. Add Erase with duplicate support.
4. Implement wildcard search with ..
5. Modify wildcard search to support ? meaning zero or one character.
6. Implement shortest root replacement.
7. Implement lexicographic autocomplete returning at most k words.
8. Implement top-K autocomplete by frequency.
9. Implement Word Search II.
10. Implement maximum XOR with a bitwise trie.

---

Section J — Interview simulation prompts

1. Explain tries to someone who only knows hash maps.
2. Prove why Search needs a terminal flag.
3. Implement core trie operations in Go.
4. Explain wildcard DFS and its worst case.
5. Walk through Word Search II on a 2x2 board.
6. Explain how you would avoid duplicate outputs.
7. Explain the memory tradeoff of [26]*node.
8. Design autocomplete for 10 million product names.
9. Design an HTTP router using a trie.
10. Explain when a sorted array beats a trie.

---

Section K — Mastery check

A learner has mastered this module when they can answer all of these without notes:

1. What invariant does a trie maintain?
2. What is the difference between a prefix node and a terminal node?
3. Why does wildcard search require DFS?
4. Why can trie + board DFS reduce repeated work compared with searching each word independently?
5. How does clearing node.word avoid duplicates?
6. How do counts enable deletion?
7. How would you handle Unicode?
8. How would you return top-K suggestions?
9. How would you reduce memory usage?
10. What is a non-string use case for tries?

Section L — Model answers for the implementation and discussion challenges

These models complete Sections I, J, and K. They are reasoning exercises, not additional registered runner problems. The four core implementations, complete references, and both test suites remain in their existing problem directories.

Section I models

1. Core operations. Initialize a root for the empty prefix. Insert creates one child per missing lowercase byte and marks the final node terminal. Search follows every byte, rejects a missing edge, then reads the terminal marker. StartsWith follows the same path but does not require terminal status. Duplicate insertion leaves a boolean terminal true; it does not create duplicate nodes. Each operation takes O(L) traversal time for length L, with at most L new nodes on insertion.
2. Counts. Store endCount and passCount. Increment root passCount once per insertion, then each traversed node’s passCount, and finally terminal endCount. Exact count reads endCount after a full traversal; prefix count reads passCount. For two app insertions and one apple, the app node has endCount 2 and passCount 3. Incrementing the root makes the empty-prefix total well-defined.
3. Deletion. First verify endCount>0 without modifying anything. Record the root-to-terminal path. Decrement every passCount along it and the terminal endCount once. Walking backward, disconnect a child only when its passCount becomes zero; stop once a positive-count shared branch is reached. A missing erase is a no-op. Erasing one app from the preceding example leaves exact count 1, prefix count 2, and apple present. O(L) time and O(L) recorded path space.
4. Dot wildcard. Search state is (node, patternIndex). A literal follows its matching child; dot tries every existing child. At the end of the pattern, accept only a terminal node. Short-circuit on the first successful branch. In the worst case, many dictionary-prefix nodes are visited; this is not always O(pattern length).
5. Optional-character wildcard. Here ? consumes zero or one stored character. From (node,i) try (node,i+1) for zero characters and (child,i+1) for every child for one character. A dot, if retained, still consumes exactly one. At pattern exhaustion require terminal status. Memoize (node,i) so different choices do not recompute the same suffix question. For dictionary ab, patterns a?b and ?b match, while a??c does not.
6. Shortest roots. For each lowercase token, follow its path and return immediately at the first terminal. If the path disappears before any terminal, return the original token. “First” means shortest because depth is prefix length. Choose whitespace semantics explicitly: the core registered problem retains its original single-space token contract; a whitespace-preserving variant must scan and copy separators, not use Fields.
7. Lexicographic output. Traverse the requested prefix, then visit terminal status before children in a through z order. Stop after k distinct words. Visiting the terminal first puts app before apple. Skip traversal entirely when k<=0 or the prefix path is absent. Runtime includes the visited subtree and the bytes copied into the output; do not label every query merely O(prefix length).
8. Frequency output. For positive frequency increments, retain a global frequency map and a capped best-k list at every prefix node, including the root. On Add, update the word’s total, then at each node remove its old cached entry if present, insert its new rank, sort by descending total and ascending word, and trim to k. Only one word’s rank improves, so the old best k plus that word contain the new best k. Decreases or deletions need a different repair strategy because an uncached word may become eligible.
9. Board search. Build a trie with terminal word IDs. From every cell, enter only the child matching its byte, mark that cell unavailable, inspect the terminal, explore four neighbors, and restore the byte before returning on every path. Clear only the emitted terminal marker to deduplicate output; keep children so longer words remain discoverable. Restoring the board permits another start and repeated calls to see the original input.
10. Maximum XOR. Represent every nonnegative integer using one fixed width sufficient for the allowed values. Insert bits from most to least significant. To query a number, prefer the opposite bit if available because a one at a higher position outweighs every possible lower-bit gain. Otherwise take the equal bit. Accumulate the XOR value, not the partner’s value. For fewer than two inputs, define the extension result as 0; duplicates may form distinct-index pairs but contribute XOR zero.

Section J models: what a strong spoken answer contains

1. A hash map remembers a whole key; a trie shares each successive prefix. For app and apple, the same three edges serve both words. Exact membership still needs a terminal marker.
2. A path exists for app after inserting apple, but app was not inserted. Path existence and terminal status answer different predicates. This one counterexample proves why the flag is necessary.
3. State the lowercase-byte domain, root initialization, missing-child branch, and terminal check before coding. Test shared prefixes, missing words, duplicates, and the agreed empty-string convention.
4. A dot branches over existing children and consumes one position. Bound work by the reachable search states or trie size, with O(L) recursion depth. A dictionary with broad shared depth can make a wildcard query much more expensive than exact lookup.
5. On rows ab and cd, abdc follows all four orthogonal edges around the square. abcd fails at the diagonal b-to-c move. Mark and restore each cell while tracing.
6. A terminal ID emitted once can be cleared for the duration of a fresh query trie, or a result set can record emitted IDs. Clearing the terminal does not remove descendants. Reusing a persistent trie across independent board queries requires resetting these markers or using per-query marks.
7. A 26-pointer child array gives direct indexing but reserves 26 slots even at sparse nodes. Maps store sparse edges but add hashing/allocation overhead. Measure actual object sizes and node degree before deciding; a pointer count alone is not a complete memory estimate.
8. Separate query shape, update rate, ranking, and memory budget. A static sorted index with two prefix bounds is a useful baseline; cached trie rankings trade memory and update work for faster top-k reads. Ten million names alone does not determine which design wins.
9. Use path segments as edges, not individual bytes. Define literal-versus-parameter priority and fallback when the literal branch later fails. Normalize slashes deliberately and reject unsupported syntax rather than treating every colon as magic.
10. A sorted array is especially attractive for static dictionaries: contiguous storage and binary-search prefix ranges avoid one heap object per character. Frequent online updates or per-prefix metadata can favor a trie, but “trie is always faster” is not a defensible answer.

Section K models: a compact mastery key

1. Each reachable node corresponds to exactly one root-to-node prefix; terminal metadata states which complete words end there.
2. A prefix node certifies a traversable path. A terminal node additionally certifies an inserted complete word.
3. A dot can match several outgoing edges, so one deterministic path is insufficient; depth-first search is one valid exploration strategy.
4. Shared dictionary prefixes let one board path serve several candidate words, and absent prefixes prune all their continuations at once. This can reduce repeated work, but does not guarantee a speedup on every tiny or adversarial instance.
5. Clearing one terminal after emitting its word prevents later paths from emitting the same word, while descendants still represent longer words.
6. Positive subtree/pass counts distinguish shared live paths from paths whose last occurrence has been erased. Verify existence before decrementing.
7. Choose a unit first: UTF-8 bytes, Unicode code points, or grapheme clusters. A map keyed by rune supports code-point edges; normalization and grapheme matching remain separate requirements.
8. Enumerate in lexical order for unranked suggestions; cache and maintain a ranked candidate list when top-k by frequency is required. State update semantics and tie rules.
9. Compare dense arrays, sparse maps/sorted edge slices, compressed paths, and a static sorted-word index using the actual dictionary and workload.
10. A fixed-width bitwise trie supports maximum-XOR queries; a segment trie supports route or directory lookup.

Supplementary practice bank and model solutions

Original Trie Problem Bank

This bank adds original, open-source-friendly problems around the same concepts. These are not copied platform statements. They are designed to teach the underlying ideas in a graduated sequence.

---

1. Prefix Notebook

Prompt

Build a notebook index that supports adding lowercase tags and checking whether a tag or tag prefix exists.

Signature

type Notebook struct { /* private state is chosen in the exercise */ }

func NewNotebook() Notebook
func (n *Notebook) Add(tag string)
func (n *Notebook) HasTag(tag string) bool
func (n *Notebook) HasPrefix(prefix string) bool

Example

Add("backend")
Add("backup")
HasTag("back") -> false
HasPrefix("back") -> true
HasTag("backend") -> true

Teaching goal

This is the same as core trie operations, but framed in product language.

Near-solution

Each node stores children and isWord. HasTag checks terminal flag. HasPrefix only checks path existence.

---

2. Prefix Counter

Prompt

Build a structure that supports duplicate words and can count exact words and prefixes.

Signature

type PrefixCounter struct { /* private state is chosen in the exercise */ }

func NewPrefixCounter() PrefixCounter
func (p *PrefixCounter) Add(word string)
func (p *PrefixCounter) CountExact(word string) int
func (p *PrefixCounter) CountPrefix(prefix string) int

Example

Add("app")
Add("apple")
Add("app")
CountExact("app") -> 2
CountPrefix("app") -> 3

Teaching goal

Shows why isWord bool is not enough for duplicates and counts.

Near-solution

Use countWord and countPrefix fields. Increment prefix count while walking every inserted character.

---

3. Erasable Dictionary

Prompt

Extend PrefixCounter with deletion. Deleting a missing word should do nothing.

Signature

func (p *PrefixCounter) Erase(word string)

Example

Add("app")
Add("apple")
Erase("app")
CountExact("app") -> 0
CountPrefix("app") -> 1
CountExact("apple") -> 1

Teaching goal

Forces learners to preserve shared prefixes.

Near-solution

First check CountExact(word) > 0. Then walk the path, decrement countPrefix, and prune a child when its countPrefix becomes zero.

---

4. Dot Pattern Dictionary

Prompt

A pattern may contain lowercase letters and .. The dot matches exactly one lowercase letter. Return whether any stored word matches the pattern.

Signature

type DotDictionary struct { /* private state is chosen in the exercise */ }

func NewDotDictionary() DotDictionary
func (d *DotDictionary) Add(word string)
func (d *DotDictionary) Match(pattern string) bool

Example

Add("code")
Add("cope")
Match("co.e") -> true
Match("c..")  -> false

Teaching goal

DFS state and base-case correctness.

Near-solution

Use recursive search (node, i). Letter follows one child. Dot tries all non-nil children. At the end, return terminal status.

---

5. Root Compressor

Prompt

Given root words and a message, replace every token with the shortest root that is its prefix. If no root matches, keep the token.

Signature

func CompressRoots(roots []string, message string) string

Example

roots = ["deb", "debug", "dev", "prod"]
message = "debugging production develops"
output = "deb prod dev"

Teaching goal

First terminal node is shortest prefix.

Near-solution

Build a trie of roots. For each token, walk until a terminal node or missing edge.

---

6. Letter Board Hunt

Prompt

Given a board of lowercase letters and a dictionary, return every dictionary word that can be formed by moving up/down/left/right without reusing a cell in the same word.

Signature

func Hunt(board [][]byte, dictionary []string) []string

Teaching goal

Trie as a pruning engine inside backtracking.

Near-solution

Build a trie. DFS from every cell. The current board path must be a trie prefix. Terminal nodes store the word and are cleared after output.

---

7. Lexicographic Suggestions

Prompt

Given a list of lowercase product names and a typed query, after each typed character return up to k lexicographically smallest product names with that prefix.

Signature

func Suggestions(products []string, query string, k int) [][]string

Example

products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"]
query = "mouse"
k = 3

output after each prefix:
"m"     -> ["mobile", "moneypot", "monitor"]
"mo"    -> ["mobile", "moneypot", "monitor"]
"mou"   -> ["mouse", "mousepad"]
"mous"  -> ["mouse", "mousepad"]
"mouse" -> ["mouse", "mousepad"]

Teaching goal

Subtree enumeration and output limiting.

Near-solution

Either sort products then use binary search, or build a trie and DFS children in a..z order after walking to each prefix node. This problem is useful because both approaches are defensible.

---

8. Hot Autocomplete

Prompt

Words have frequencies. For a prefix, return the top k words by frequency, breaking ties lexicographically.

Signature

type HotAutocomplete struct { /* private state is chosen in the exercise */ }

func NewHotAutocomplete(k int) HotAutocomplete
func (h *HotAutocomplete) Add(word string, frequency int)
func (h *HotAutocomplete) Query(prefix string) []string

Teaching goal

Cached metadata on trie nodes and space-time tradeoffs.

Near-solution

For each insertion, update a capped sorted top-K list on every node along the word path. Query walks the prefix and returns that node's cached list.

---

9. Segment Router

Prompt

Build a simple HTTP route matcher. Routes are slash-separated segments. A segment starting with : matches any one segment.

Signature

type Router struct { /* private state is chosen in the exercise */ }

func NewRouter() Router
func (r *Router) Add(pattern string, handler string)
func (r *Router) Match(path string) (handler string, ok bool)

Example

Add("/users/:id", "getUser")
Add("/users/:id/orders", "getOrders")
Match("/users/42") -> "getUser", true
Match("/users/42/orders") -> "getOrders", true

Teaching goal

Shows that trie alphabets can be path segments, not characters. Also introduces wildcard edges in a backend-relevant setting.

Near-solution

Use map[string]*node for literal children plus one parameter child. Match the literal branch first, then backtrack to the parameter branch if the entire literal suffix fails; a local literal edge is not sufficient to commit. Terminal node stores handler.

---

10. Binary XOR Analyzer

Prompt

Given non-negative integers, find the maximum XOR value obtainable from any pair.

Signature

func MaxPairXOR(nums []int) int

Example

nums = [3, 10, 5, 25, 2, 8]
output = 28 // 5 ^ 25

Teaching goal

Tries over bits.

Near-solution

Insert every number into a bitwise trie. For each number, greedily walk the opposite bit when possible from most significant to least significant bit.

---

11. One-Typo Search

Prompt

A search pattern matches a stored word if it has the same length and differs in at most one character.

Signature

type TypoDictionary struct { /* private state is chosen in the exercise */ }

func NewTypoDictionary() TypoDictionary
func (t *TypoDictionary) Add(word string)
func (t *TypoDictionary) MatchOneTypo(pattern string) bool

Example

Add("stone")
MatchOneTypo("stoke") -> true
MatchOneTypo("money") -> false

Teaching goal

DFS with an extra state variable.

Near-solution

State is (node, i, editsUsed). If current character matches, continue without edit. You may also branch to other children if editsUsed == 0.

---

12. Memory Budget Trie

Prompt

You are given a large dictionary and must support prefix existence checks under a memory budget. Propose and implement one memory-conscious representation.

Teaching goal

Makes learners compare [26]*node, map[byte]*node, sorted child slices, and compressed tries.

Near-solution

There is no single answer. For sparse lowercase data, a sorted slice of (byte, *node) or map[byte]*node may save memory. For static data, a sorted array with binary search may beat a trie.

Model solutions and precise extension contracts

The signatures above describe practice APIs, not compiled starter files or new manifest problems. The following models supply the missing decisions and complete algorithms. These extension-specific choices do not change the four registered trie problems.

1. Prefix Notebook model

Use lowercase-byte edges, a root, and a boolean terminal. Add walks or creates every edge and sets terminal at the end. HasTag requires terminal; HasPrefix requires only a complete walk. Repeated Add is idempotent. As in the core trie’s path convention, the empty prefix exists at the root even before inserting a word. If empty tags are allowed for this extension, Add("") marks the root terminal. Missing edges return false rather than being created during a read. O(L) traversal; at most total inserted-byte count plus one nodes.

2. Prefix Counter model

Use the same edges plus endCount and passCount. Every Add increments passCount at root and along the entire word path, then endCount at the endpoint. CountExact reads endCount, and CountPrefix reads passCount; a missing path returns zero. Thus CountPrefix("") is the number of inserted occurrences, including duplicates. The invariant is that passCount equals the total terminal multiplicity in that subtree. No recursive subtree recount is needed for a query.

3. Erasable Dictionary model

Read the full path first and stop without changes if the endpoint is missing or has zero endCount. Decrement endCount once and every path node’s passCount once. Remove zero-count edges from the leaf upward, leaving every positive-count shared branch attached. Example: after app, app, apple, one erase of app leaves counts 1 and 2 at that node; erasing a nonexistent ape changes nothing. A count cannot become negative under this existence-first protocol. O(L) traversal and recorded path space.

4. Dot Pattern Dictionary model

Insertion is ordinary terminal-marking insertion. Match performs DFS on (node,i). At i==len(pattern), return terminal. For a letter, recurse only into its matching nonnil child; for dot, recurse into each nonnil child and accept if any accepts. Every edge consumes exactly one pattern position, so a prefix cannot satisfy a longer pattern and an internal nonterminal cannot satisfy a shorter one. Depth is O(L), and work is proportional to explored trie edges/states, which may be exponential in wildcard count until capped by the stored trie’s size.

5. Root Compressor model

For this extension, use nonempty lowercase roots and lowercase tokens separated by a single ASCII space, matching the core problem’s narrow contract. Insert roots. For each token, stop at the earliest terminal reached and output that prefix; otherwise output the original token. Join with one space. Empty input returns empty output. If an exact-whitespace variant is chosen instead, scan maximal lowercase tokens while copying every intervening separator verbatim; do not claim the two variants have identical behavior. Construction is linear in root bytes; replacement traversal and output are linear in message bytes.

6. Letter Board Hunt model

Use a rectangular board, nonempty lowercase dictionary words, orthogonal moves, no cell reuse within a path, and distinct output words in any order. Build a fresh trie per Hunt call. For each cell, follow its matching trie edge before marking it; at a terminal emit its word and clear that terminal; then search unvisited neighbors and restore the original cell. Clearing a terminal does not prune longer descendants. A fresh trie makes repeated calls independent. The board is unchanged on return. Trie construction shares dictionary prefixes, but the board search still has exponential worst-case path exploration in the maximum usable word length.

7. Lexicographic Suggestions model

Deduplicate product names, sort them, and keep the list read-only. After each query byte, find the first product >= that prefix by lower-bound search, then copy at most k consecutive products while each still has the prefix. Append an empty result for all later prefixes after a missing prefix. For k<=0, each prefix receives an empty list. This sorted-array model is complete without a trie and is particularly simple for static input. Account for byte comparisons in sorting/search and for output bytes. A trie alternative walks the prefix then performs bounded lexicographic DFS; the order is terminal first, then child bytes ascending.

8. Hot Autocomplete model

Choose this explicit update contract: Add(word,frequency) adds a strictly positive delta to that word’s cumulative frequency; k is fixed and nonnegative. Query returns up to k distinct stored words sorted by descending cumulative frequency, then ascending lexical order. Cache a best-k list at every node, including root. After a word’s count increases, the only candidate newly able to enter a cache is that word; merge it with the previous cache, rerank, and trim. Query returns a copy so callers cannot mutate cached state. With simple sorting, updating length L costs O((L+1)klog(k+1)) ranking work plus word-comparison costs; query traverses the prefix and copies up to k strings. Frequency decreases or replacing totals are a different contract and require broader cache repair.

9. Segment Router model

Use canonical paths beginning with /, with no empty interior segments or trailing slash except root. A parameter segment starts with : and consumes exactly one nonempty segment. Each node has literal children, at most one parameter child, a terminal flag, and a handler string. Adding the same normalized pattern replaces its handler. Matching recursively tries the literal child first; if that entire suffix fails to reach a terminal, try the parameter child. A local literal match must not forbid fallback. For routes /a/x/z and /a/:id/y, path /a/x/y must fall back to the parameter route. Among complete matches, literal preference at the earliest differing segment determines priority. Root can be a terminal route. Search can branch; do not promise a single-path O(segment count) bound without stronger ambiguity restrictions.

10. Binary XOR Analyzer model

Use nonnegative machine ints and a fixed width covering all their value bits. Insert every value’s bits from high to low into a two-child trie. For each input, walk the trie preferring the opposite bit and set that result bit when the opposite branch exists. The preference is optimal because one higher-bit gain exceeds the sum of all lower gains. Take the largest completed XOR. Distinct index pairs are intended; for fewer than two inputs return 0. A number pairing with its own inserted copy yields zero, so it cannot defeat a positive distinct-pair maximum; all-equal arrays correctly return zero. Time and node bound are O(nW), where W is the chosen fixed width.

11. One-Typo Search model

“At most one” includes an exact match. Traverse states (node,i,editsUsed). For every outgoing edge, add zero if its byte matches pattern[i] and one otherwise; recurse only while the sum is <=1. Accept only when both the pattern is exhausted and the node is terminal. This permits a substitution but no insertion or deletion, so differing lengths never match. Test exact stone, one-substitution stoke, and two-substitution stake against stored stone: true, true, false. The recursion depth is pattern length; work is the number of visited compatible trie states.

12. Memory Budget Trie model

For a concrete static solution, store a sorted deduplicated string slice rather than per-character nodes. For a nonempty prefix, lower-bound it and check whether the candidate starts with that prefix. Adopt the same empty-prefix path convention as the core trie and return true for "". This implementation uses O(number of distinct words) slice headers/references plus retained string bytes and no per-character heap objects. Preprocessing needs sorting; insertion is not cheap unless the index is rebuilt or a different dynamic structure is chosen. Binary-search comparisons still read bytes, so cost depends on common-prefix length. Measure retained heap and query latency on the actual corpus against a dense trie and a sparse representation; no particular memory budget or ten-million-word capacity is guaranteed without that measurement.

Optional mentor guide

Trie Module Mentor Notes

This document explains how to teach the module so learners go from zero to professional competence.

---

Teaching philosophy

Do not start with code. Start with the pain.

The pain is this:

A hash set can answer exact membership, but it cannot cheaply reason about unfinished strings.

Tries solve unfinished-string questions:

Does this prefix exist?
What completions are possible?
Can this board path still become any target word?
Where is the shortest root?

Once learners understand that, the code becomes natural.

---

Recommended module sequence

Session 1 — Prefixes and the invariant

Goal: learners understand that nodes represent prefixes.

Content:

1. Draw a trie for app, apple, apply, bat.
2. State the invariant.
3. Manually answer Search and StartsWith questions.
4. Implement core trie operations.

Checkpoint:

Learner can explain why Search("app") is false after only inserting "apple".

---

Session 2 — Counts and deletion

Goal: learners move beyond isWord bool.

Content:

1. Add countWord and countPrefix.
2. Insert duplicates.
3. Delete safely.
4. Explain why shared prefixes cannot be blindly removed.

Checkpoint:

Learner can erase app while keeping apple intact.

---

Session 3 — Wildcards

Goal: learners design recursive trie DFS.

Content:

1. Define state (node, i).
2. Letter follows one child.
3. Dot branches over all children.
4. Base case returns terminal status.

Checkpoint:

Learner can explain why Search("ba") must be false after adding "bad".

---

Session 4 — Replace Words

Goal: learners use first terminal node semantics.

Content:

1. Insert roots.
2. Walk each sentence token.
3. Stop at first terminal.
4. Discuss whitespace-preserving variant.

Checkpoint:

Learner can explain why bat beats bath for bathroom.

---

Session 5 — Word Search II

Goal: learners experience the main trie “aha”.

Content:

1. Show why per-word DFS repeats work.
2. Build trie once.
3. DFS board paths while walking trie.
4. Prune missing prefixes.
5. Store terminal word and clear it after output.

Checkpoint:

Learner can trace one found word and one pruned path.

---

Session 6 — Professional extensions

Goal: learners generalize tries.

Content:

1. Autocomplete.
2. Top-K cached suggestions.
3. Bitwise trie.
4. Segment router.
5. Memory tradeoffs.

Checkpoint:

Learner can design a trie node from requirements instead of copying a template.

---

How much answer to reveal

This module intentionally uses near-solutions. That is acceptable because the learning goal is structural understanding, not puzzle withholding.

Use this reveal ladder:

1. Ask learner to restate the invariant.
2. Give the node fields.
3. Give the loop shape.
4. Let learner fill base cases.
5. If stuck, show the full solution and ask them to trace it.
6. Then make them implement a small variant without looking.

The variant is where transfer happens.

---

Common learner failure modes

Failure: “Every node is a word.”

Fix: Draw apple, then ask about app.

Failure: “Wildcard is just one if statement.”

Fix: Draw branching for .ad over bad, dad, mad.

Failure: “Word Search II is just DFS.”

Fix: Compare per-word DFS with trie-pruned DFS on shared prefixes.

Failure: “I memorized [26]*node.”

Fix: Ask for Unicode, API routes, and bitwise XOR.

Failure: “Deletion deletes too much.”

Fix: Use app, apple, apply. Delete apple; verify app and apply.

---

Rubric

Beginner

Can:

• Draw a small trie.
• Implement insert/search/startsWith with help.
• Explain prefix vs word.

Cannot yet:

• Design node metadata independently.
• Handle wildcard DFS confidently.
• Reason about deletion.

Intermediate

Can:

• Implement core operations from memory.
• Solve wildcard search.
• Solve Replace Words.
• Explain complexity.

Needs work on:

• Board search pruning.
• Memory tradeoffs.
• Counts/deletion.

Advanced

Can:

• Solve Word Search II cleanly.
• Add counts/deletion.
• Design autocomplete.
• Explain [26]*node vs map tradeoffs.

Needs work on:

• Production constraints.
• Compressed tries.
• Large-scale top-K design.

Professional

Can:

• Choose or reject trie appropriately.
• Build trie variants over characters, bits, path segments, or tokens.
• Design terminal metadata from output requirements.
• Prove correctness from invariants.
• Optimize only after correctness.

---

Suggested assessments

Assessment 1 — Core implementation

Implement Trie in Go with tests for:

apple/app
shared prefixes
duplicate insert
missing branch

Assessment 2 — Counts and delete

Implement duplicate-aware count and delete.

Must pass:

Add app
Add app
Add apple
Erase app
CountExact app = 1
CountPrefix app = 2

Assessment 3 — Wildcard

Implement dot wildcard.

Must pass:

Add bad, dad, mad
.ad -> true
b.. -> true
.. -> false

Assessment 4 — Board search

Implement trie-pruned board search.

Must pass:

board = ["ab", "cd"]
words = ["ab", "abdc", "acdb", "ad"]
found = ["ab", "abdc", "acdb"] under standard up/down/left/right movement

Note: For standard up/down/left/right, abdc is valid as a->b->d->c, while abcd is not valid because b->c is diagonal.

Assessment 5 — Design discussion

Ask:

Design autocomplete for 10 million products with frequent queries and occasional updates.

Expected answer:

• Trie can work.
• Cache top-K at nodes if query latency matters.
• Discuss memory cost.
• Consider sorted array if data is static.
• Consider search infrastructure if ranking is complex.

---

Quality bar for open-source module

A strong module should include:

1. Conceptual explanation.
2. Invariant.
3. Brute force contrast.
4. Clean reference implementation.
5. Guided starter.
6. Public and hidden tests.
7. Trace walkthrough.
8. Correctness proof.
9. Complexity with practical caveats.
10. Pitfall checklist.
11. Variants and extensions.
12. Exercises with answers.
13. Capstone project.

Use this as an assessment checklist rather than a claim that reading one module establishes production competence.

Replacement integration and assessment evidence

The six sessions above remain a suggested mentoring sequence, not a claim that each learner needs the same number of sessions. The registered module still contains the same four problems, followed by the new exact-graded quiz. Counts, deletion, autocomplete, router, XOR, typo, and memory exercises are optional transfer work with complete algorithmic model answers in the practice bank and drills; they are not separately graded runner tasks.

Assess three distinct outcomes: a correct result, a correct invariant explanation, and an independent reconstruction. Passing a quiz checks a small set of objective facts, not all three outcomes. Ask the learner to invent a counterexample to a broken version: missing terminal check, un-restored board cell, or literal-only router commitment. Compare their case with the model key before showing code.

For implementation assessment, run the original and new tests, inspect pointer or mutation behavior where applicable, then ask for the specific assumption that makes each test legitimate. Lowercase-byte indexing is a contract decision; Go does allow rune-typed array indices. Do not teach a false type restriction as a reason to avoid Unicode.

Open the live module quiz · Drills and model answers in the lesson

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Trie Foundations (Interview 150)

Mental model

Core patterns

Pattern: Prefix insertion/search

Pattern: Wildcard DFS

Pattern: Dictionary pruning

Pattern: Shortest root replacement

When to reach for this module

Common failures

Learner experience: how to make this topic stick