Trie / Prefix Tree

A trie is a tree-shaped index for strings. It turns repeated prefixes into shared structure.

This module teaches tries as a professional tool, not as a memorized LeetCode trick. By the end, a learner should be able to recognize prefix-shaped problems, design the node fields needed by the problem, prove the invariant, implement the solution in Go, and reason about memory/performance tradeoffs.

What you should be able to do after this module

You should be able to:

1. Explain why a hash set solves exact lookup but not efficient prefix exploration.
2. Implement Insert, Search, and StartsWith from first principles.
3. State the core trie invariant without hand-waving.
4. Design node fields such as isWord, word, countWord, countPrefix, value, or topK based on the problem.
5. Use DFS on a trie for wildcard matching.
6. Combine a trie with grid backtracking to prune impossible word-search paths.
7. Implement shortest-prefix replacement.
8. Analyze real complexity, including memory overhead and branching cost.
9. Know when not to use a trie.
10. Extend a trie to autocomplete, deletion, prefix counts, and bitwise XOR search.

The problem tries are actually solving

Imagine you have these words:

app
apple
apply
bat
batch
bath

A hash set stores them as separate complete values. That is fine for Search("apple"), but weak for questions like:

Does any word start with "ap"?
List all words starting with "bat".
While walking a board, can the path "apq" still become any word?
What is the shortest root that prefixes "battery"?

Those questions are not about one finished string. They are about partial progress through a string.

A trie makes partial progress explicit. The root represents the empty prefix. Every step down an edge adds one character. The path from the root to a node spells a prefix.

(root)
 ├── a
 │   └── p
 │       └── p  [word: app]
 │           ├── l
 │           │   ├── e [word: apple]
 │           │   └── y [word: apply]
 └── b
     └── a
         └── t [word: bat]
             ├── c
             │   └── h [word: batch]
             └── h [word: bath]

The win is sharing. The prefix app is stored once, even though it participates in app, apple, and apply.

The core invariant

The central invariant is:

For any node n, the path from the root to n spells exactly one prefix. If n.isWord == true, that prefix is also a complete inserted word.

Everything else follows from that.

For a node reached by walking "app":

path(root -> node) = "app"
node.isWord = true    means "app" was inserted
node.isWord = false   means "app" is only a prefix so far
node.children['l'] != nil means at least one inserted word starts with "appl"

Professional trie work is mostly about protecting this invariant while changing the node shape for each problem.

Vocabulary

Choosing the node representation

The node fields should come from the question. Do not blindly copy a single Node struct everywhere.

Fixed lowercase English alphabet

Use this when all inputs are a-z:

type node struct {
    children [26]*node
    isWord   bool
}

Pros: fast, simple, no hashing, predictable.

Cons: memory-heavy when most nodes have only one or two children.

Dynamic alphabet

Use this when characters are not limited to a-z, or the alphabet is sparse:

type node struct {
    children map[rune]*node
    isWord   bool
}

Pros: flexible, handles Unicode and arbitrary alphabets.

Cons: map overhead, slower constant factors, more allocation.

Store full word at terminal nodes

Useful in word search because you want to output the matched word without reconstructing the path:

type node struct {
    children [26]*node
    word     string // non-empty means terminal
}

Store counts

Useful for prefix counts, deletion, and multiset behavior:

type node struct {
    children    [26]*node
    countPrefix int // number of inserted words passing through this node
    countWord   int // number of inserted words ending exactly here
}

Store top suggestions

Useful for autocomplete when each prefix should return top-K results quickly:

type node struct {
    children [26]*node
    top      []Suggestion // kept sorted, capped at K
    isWord   bool
}

Decision guide: trie or something else?

Pattern 1: Core trie operations

Use this when you need insertion, exact-word lookup, and prefix lookup.

Problems:

• implement-trie-prefix-tree
• Prefix phonebook
• Dictionary membership with prefix checks
• Command palette prefix filter

Mental model

Insert("apple") creates or reuses this path:

root -> a -> p -> p -> l -> e

The final node is marked as a word. Intermediate nodes are prefixes but not necessarily words.

This distinction is the source of many bugs:

Insert("apple")
Search("app")      -> false
StartsWith("app")  -> true

app exists as a path, but it has not been marked as a complete word.

Go implementation

type Trie struct {
    root *trieNode
}

type trieNode struct {
    children [26]*trieNode
    isWord   bool
}

func Constructor() Trie {
    return Trie{root: &trieNode{}}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if node.children[idx] == nil {
            node.children[idx] = &trieNode{}
        }
        node = node.children[idx]
    }
    node.isWord = true
}

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

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

func (t *Trie) find(s string) *trieNode {
    node := t.root
    for i := 0; i < len(s); i++ {
        idx := s[i] - 'a'
        if node.children[idx] == nil {
            return nil
        }
        node = node.children[idx]
    }
    return node
}

Why Search and StartsWith are different

Both walk a path. They differ only at the end.

Search("app") asks:

Does the path exist, and is the final node terminal?

StartsWith("app") asks:

Does the path exist?

That is it. The whole core trie problem is one helper plus one terminal check.

Trace

Operations:

Insert("apple")
Search("apple")
Search("app")
StartsWith("app")
Insert("app")
Search("app")

Walk:

Insert("apple")
- root has no 'a', create it
- 'a' has no 'p', create it
- first 'p' has no second 'p', create it
- second 'p' has no 'l', create it
- 'l' has no 'e', create it
- mark 'e'.isWord = true

Search("apple")
- path exists to 'e'
- 'e'.isWord is true
- return true

Search("app")
- path exists to second 'p'
- second 'p'.isWord is false
- return false

StartsWith("app")
- path exists to second 'p'
- no terminal check
- return true

Insert("app")
- path already exists
- mark second 'p'.isWord = true

Search("app")
- path exists and terminal flag true
- return true

Correctness argument

Insertion preserves the invariant because it creates exactly the missing nodes for each prefix of the inserted word and marks only the full word endpoint as terminal.

Search is correct because there is exactly one possible path for a fixed string in a trie with deterministic character edges. If any required child is missing, no inserted word has that prefix, so the exact word cannot exist. If the path exists, the word exists exactly when the endpoint is terminal.

StartsWith is correct because a path exists for a prefix exactly when at least one inserted word has created that path.

Complexity

Let L be the length of the input word or prefix.

The trie as a whole uses O(total inserted characters) nodes in the worst case, but fewer when prefixes are shared.

Important practical note: [26]*node can use more memory than a map for sparse tries. The asymptotic space hides constant factors.

Common bugs

1. Returning true for Search("app") after inserting only "apple".
2. Forgetting to initialize the root in Constructor.
3. Replacing an existing child instead of reusing it.
4. Using rune loops but indexing [26] with bytes incorrectly.
5. Ignoring input constraints. If the problem says lowercase a-z, byte indexing is fine. If not, it is not.

Micro-drills

1. After inserting "a", "an", "ant", what should Search("an") return?
2. After inserting "ant", what should StartsWith("an") return?
3. Which node gets isWord = true when inserting "banana"?
4. Why is find useful?
5. How many new nodes are created when inserting "apple" after "app" already exists?

Answers:

1. true if "an" was inserted, otherwise false.
2. true.
3. The node reached after the final a.
4. It removes duplication between exact search and prefix search.
5. Two new nodes: l and e.

Pattern 2: Prefix counts and deletion

This pattern is not always in beginner modules, but it is important for professional use. Real data structures often need to count or remove entries.

Use when you need:

CountWordsEqualTo("app")
CountWordsStartingWith("app")
Erase("app")

Node fields

type node struct {
    children    [26]*node
    countPrefix int
    countWord   int
}

Meaning:

countPrefix = how many inserted words pass through this node
countWord   = how many inserted words end at this node

If duplicates are allowed, inserting "app" twice makes countWord == 2 at the terminal node.

Insert with counts

func insert(root *node, word string) {
    cur := root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if cur.children[idx] == nil {
            cur.children[idx] = &node{}
        }
        cur = cur.children[idx]
        cur.countPrefix++
    }
    cur.countWord++
}

Whether the root should count all words is a design choice. Most interview implementations do not need root counts unless empty-prefix queries are allowed.

Counting

func countEqual(root *node, word string) int {
    cur := walk(root, word)
    if cur == nil {
        return 0
    }
    return cur.countWord
}

func countPrefix(root *node, prefix string) int {
    cur := walk(root, prefix)
    if cur == nil {
        return 0
    }
    return cur.countPrefix
}

Deletion

Deletion has two separate tasks:

1. Decrease counts so future queries are correct.
2. Optionally remove nodes that are no longer used.

A safe version first confirms the word exists.

func erase(root *node, word string) {
    if countEqual(root, word) == 0 {
        return
    }
    cur := root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        child := cur.children[idx]
        child.countPrefix--
        if child.countPrefix == 0 {
            cur.children[idx] = nil
            return
        }
        cur = child
    }
    cur.countWord--
}

Why deletion is easy to get wrong

Suppose the trie contains:

app
apple

If you erase app, you must not delete the app node, because apple still needs it. You only reduce countWord at app.

If you erase apple, you may prune the l -> e chain, but not the shared app prefix.

Counts tell you whether a node is still needed.

Pattern 3: Wildcard search

Use when a pattern may include a wildcard such as . meaning “any one character”.

Problem:

• design-add-and-search-words-data-structure

Example:

Stored words: bad, dad, mad
Search("bad") -> true
Search(".ad") -> true
Search("b..") -> true
Search("..")  -> false

The key shift

Without wildcards, every character gives exactly one next node.

With . you do not know which child to take, so you try all possible children.

The search state is:

(node, i)

where:

node = current trie node
 i   = index in the search pattern

Recursive logic

func searchFrom(node *wordNode, word string, i int) bool {
    if node == nil {
        return false
    }
    if i == len(word) {
        return node.isWord
    }

    ch := word[i]
    if ch != '.' {
        return searchFrom(node.children[ch-'a'], word, i+1)
    }

    for _, child := range node.children {
        if child != nil && searchFrom(child, word, i+1) {
            return true
        }
    }
    return false
}

Base case

This is the most important line:

if i == len(word) {
    return node.isWord
}

When the pattern is exhausted, a prefix is not enough. You need to be exactly at a terminal word.

That is why this must be false:

AddWord("bad")
Search("ba") -> false

The path exists, but the pattern ended too early.

Trace: Search(".ad")

Trie contains:

bad
dad
mad

Search:

state(root, 0), pattern[0] = '.'
- try child 'b'
  state(node("b"), 1), pattern[1] = 'a'
  - follow 'a'
    state(node("ba"), 2), pattern[2] = 'd'
    - follow 'd'
      state(node("bad"), 3)
      i == len(pattern), node.isWord == true
      return true

The search stops after finding one valid branch. It does not need to explore dad or mad.

Complexity

Let L be pattern length.

• No wildcards: O(L).
• One wildcard near a dense node: up to 26 branches at that position.
• All wildcards: worst case can visit many trie nodes up to depth L.

A precise way to say it:

Time = number of trie states reachable by the pattern

The commonly stated upper bound O(26^L) is safe but often pessimistic because nonexistent children are pruned.

Professional optimizations

1. Store words by length. If no word of the requested length exists, return false immediately.
2. Store a child bitmask to iterate existing children faster.
3. Memoization is rarely useful for a normal trie because a tree has one parent per node, but it can matter in DAG-like compressed structures.
4. Avoid allocating substrings inside recursion; pass an index.

Pattern 4: Shortest prefix replacement

Use when dictionary roots replace longer words.

Problem:

• replace-words

Example:

dictionary = ["cat", "bat", "rat"]
sentence   = "the cattle was rattled by the battery"
result     = "the cat was rat by the bat"

Why a trie fits

For each sentence word, you walk from the root. The first terminal node you encounter is the shortest valid root.

For "cattle":

c -> a -> t [terminal]

Stop immediately. Do not keep looking for a longer root.

Core function

func findRoot(root *node, word string) string {
    cur := root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if cur.children[idx] == nil {
            return ""
        }
        cur = cur.children[idx]
        if cur.isWord {
            return word[:i+1]
        }
    }
    return ""
}

Correctness idea

The trie path reads prefixes in increasing length order:

c, ca, cat, catt, cattl, cattle

Therefore, the first terminal node encountered must be the shortest dictionary root that prefixes the word.

Practical note about spaces

A simple implementation usually uses:

parts := strings.Fields(sentence)

That normalizes whitespace. For most coding-platform versions, the input is a normal space-separated sentence, so this is fine.

If a production requirement says “preserve exact whitespace and punctuation,” then do not use strings.Fields. Scan tokens and separators separately with a strings.Builder.

Pattern 5: Trie + grid backtracking

Use when you must find many dictionary words inside a board of characters.

Problem:

• word-search-ii

Example:

board = [
  "oaan",
  "etae",
  "ihkr",
  "iflv",
]
words = ["oath", "pea", "eat", "rain"]
result = ["oath", "eat"]

Why the naive approach is weak

A naive approach runs a separate board DFS for every word.

for word in words:
    search board for word

If there are 30,000 words, this repeats huge amounts of work.

The trie approach flips the direction:

Build one trie from all words.
Run DFS from each board cell once.
During DFS, stop immediately when the current path is not a prefix of any word.

The trie gives a cheap answer to:

Can this partial board path still become any target word?

If no, prune.

State

A DFS state is:

(r, c, trieNode)

Where:

(r, c)    = current board cell
trieNode = node representing the prefix before consuming board[r][c]

After reading the board character, move to the next trie node.

ch := board[r][c]
next := node.children[ch-'a']
if next == nil { return }

Reference shape

func FindWords(board [][]byte, words []string) []string {
    if len(board) == 0 || len(words) == 0 {
        return []string{}
    }

    root := &trieNode{}
    for _, w := range words {
        insert(root, w)
    }

    res := []string{}
    for r := range board {
        for c := range board[r] {
            dfs(board, r, c, root, &res)
        }
    }
    return res
}

Terminal nodes store the full word:

type trieNode struct {
    children [26]*trieNode
    word     string
}

This avoids carrying a path string or allocating repeatedly.

DFS

func dfs(board [][]byte, r, c int, node *trieNode, res *[]string) {
    ch := board[r][c]
    if ch == '#' {
        return
    }

    next := node.children[ch-'a']
    if next == nil {
        return
    }

    if next.word != "" {
        *res = append(*res, next.word)
        next.word = "" // avoid duplicate output
    }

    board[r][c] = '#'

    if r > 0 {
        dfs(board, r-1, c, next, res)
    }
    if r+1 < len(board) {
        dfs(board, r+1, c, next, res)
    }
    if c > 0 {
        dfs(board, r, c-1, next, res)
    }
    if c+1 < len(board[0]) {
        dfs(board, r, c+1, next, res)
    }

    board[r][c] = ch
}

Why marking visited works

The board says a cell may be used at most once per word. Marking board[r][c] = '#' temporarily removes the cell from the current path. Restoring it afterward makes it available for other paths.

This is backtracking:

choose cell
explore consequences
undo choice

Duplicate handling

Suppose words = ["ab", "ab"] or the same word appears from multiple board paths.

If you simply append every time you reach a terminal node, duplicates can appear. A clean trick is:

if next.word != "" {
    res = append(res, next.word)
    next.word = ""
}

Clearing the word means “we have already output this dictionary word.”

Trace: finding oath

board =
  o a a n
  e t a e
  i h k r
  i f l v

word = oath

Path:

(0,0) 'o' -> prefix "o" exists
(0,1) 'a' -> prefix "oa" exists
(1,1) 't' -> prefix "oat" exists
(2,1) 'h' -> word "oath" found

A wrong path prunes early:

(0,0) 'o'
(1,0) 'e' -> prefix "oe" does not exist
stop immediately

This early stop is the whole point of the trie.

Complexity

Let:

R = rows
C = columns
L = max word length
T = total characters in words

Building the trie: O(T) time and space.

DFS worst case: O(R*C*4^L) is a safe upper bound, but with visited cells it is closer to O(R*C*3^(L-1)) after the first step, and in practice the trie prunes many branches.

A more honest professional statement:

Time = O(T + number of board DFS states whose path is a dictionary prefix)

That is what the trie controls.

Optimizations after correctness

Do these only after the clean version works:

1. Store a child count and prune leaf nodes after words are found.
2. Deduplicate words before building the trie.
3. Skip starting cells whose character is not a root child.
4. Store children in a compact map if the alphabet is large.
5. Sort words by length only if using alternative approaches; the trie does not need it.

Pattern 6: Autocomplete and search suggestions

Use when a prefix should return matching words, often sorted or ranked.

Examples:

Input words: mobile, mouse, moneypot, monitor, mousepad
Query typed so far: "mouse"
After "m":     mobile, moneypot, monitor
After "mo":    mobile, moneypot, monitor
After "mou":   mouse, mousepad
After "mous":  mouse, mousepad
After "mouse": mouse, mousepad

There are two common designs.

Design A: DFS from prefix node

1. Build trie.
2. Walk to prefix node.
3. DFS subtree and collect words.
4. Stop after K results if lexicographic order is desired and children are visited a to z.

Good when:

• Dictionary is moderate size.
• Queries are not extremely frequent.
• K is small.

Cost:

O(prefix length + size of explored subtree)

Design B: cache top-K at every node

During insertion, update top suggestions on every node along the path.

Good when:

• Many queries.
• Need low-latency suggestions.
• K is small and fixed.

Cost:

Insert: O(word length * costToMaintainTopK)
Query:  O(prefix length + K)
Space:  O(total characters * K)

Professional tradeoff

Caching top-K at each node is a space-time tradeoff. It is not “more advanced” by default. It is better only when query volume justifies extra memory and update cost.

Pattern 7: Bitwise trie for maximum XOR

A trie does not have to store letters. It can store bits.

Problem shape:

Given numbers, find two numbers with maximum XOR.

XOR is maximized by choosing opposite bits as early as possible from the most significant bit.

For 32-bit integers, build a trie of bit paths:

bit 31 -> bit 30 -> ... -> bit 0

For each number x, walk the trie and prefer the opposite bit at every level.

func bestXOR(root *bitNode, x int) int {
    cur := root
    ans := 0
    for b := 31; b >= 0; b-- {
        bit := (x >> b) & 1
        want := bit ^ 1
        if cur.child[want] != nil {
            ans |= 1 << b
            cur = cur.child[want]
        } else {
            cur = cur.child[bit]
        }
    }
    return ans
}

This is the same trie idea:

prefix of characters -> prefix of bits

The alphabet is just {0,1}.

Pattern 8: Compressed tries and radix trees

A normal trie can waste memory when it has long chains with no branching.

For example:

internationalization

If no other word shares most of that path, a normal trie stores one node per character.

A compressed trie stores edge labels as strings:

root -> "internationalization"

If another word shares a prefix, the edge is split.

Compressed tries are useful in production systems such as routers, IP prefix indexes, and large dictionaries. For interview problems, plain tries are usually simpler and sufficient.

A professional trie design process

When facing a new trie problem, ask these questions in order.

1. What is the alphabet?

lowercase letters?
uppercase and lowercase?
Unicode?
path segments?
bits?

This decides [26]*node, map[rune]*node, map[string]*node, or [2]*node.

2. What does a terminal node need to store?

bool isWord?
full word string?
frequency?
value?
list of IDs?
countWord?

This comes from the output requirement.

3. Are duplicates meaningful?

If yes, isWord bool is insufficient. Use countWord.

4. Are deletions needed?

If yes, use counts or reference counters.

5. Is output top-K, all matches, or existence?

• Existence: terminal bool is enough.
• All matches: DFS subtree.
• Top-K: maybe cache top-K per node.

6. What must be pruned?

In grid search, prune when no child exists. In wildcard search, prune missing children and length mismatch. In replacement, stop at first terminal.

Problem ladder

This ladder is designed to move from barely knowing tries to professional comfort.

Level 0: Recognition

Goal: know when a trie is even relevant.

Exercises:

1. For each problem statement, classify: hash set, trie, sorting, or graph search.
2. Explain why exact lookup does not solve prefix enumeration.
3. Draw the trie for five words with shared prefixes.

Level 1: Core mechanics

Problems:

1. Implement Trie.
2. Count words equal to / starting with.
3. Delete from a trie with duplicate words.

Skills:

• Path walking.
• Terminal flags.
• Prefix counts.
• Safe deletion.

Level 2: Controlled branching

Problems:

1. Add and Search Word with . wildcard.
2. Search with exactly one typo allowed.
3. Search with ? matching zero or one character.

Skills:

• DFS state design.
• Base cases.
• Branching complexity.
• Pruning.

Level 3: Trie as a pruning engine

Problems:

1. Word Search II.
2. Boggle-style board with score.
3. DNA grid search.

Skills:

• Backtracking.
• Visited markers.
• Terminal storage.
• Duplicate removal.

Level 4: Output design

Problems:

1. Replace Words.
2. Search Suggestions.
3. Top-K autocomplete by frequency.
4. API route matching by path segment.

Skills:

• Shortest terminal.
• Subtree enumeration.
• Cached suggestions.
• Segment-based tries.

Level 5: Advanced variants

Problems:

1. Maximum XOR of two numbers.
2. Persistent trie snapshots.
3. Compressed radix tree.
4. Memory-limited autocomplete.

Skills:

• Non-character alphabets.
• Persistence.
• Compression.
• Production tradeoffs.

Problem mapping for this pack

Recommended additions:

Deep walkthrough: from brute force to trie in Word Search II

The most important “aha” problem in this module is Word Search II.

Suppose:

R*C = 144 cells
words = 30,000
average length = 8

A per-word DFS starts a board search 30,000 times. Many words share prefixes, but the algorithm forgets that.

Example words:

oath
oatmeal
oasis
oar
eat
earth
earn

When the board path starts with oa, every word that does not start with oa is irrelevant. A trie makes that filtering immediate.

Instead of asking:

Can I find word W?

ask:

The board has currently spelled prefix P. Does any target word start with P?

If no, stop. If yes, continue.

This is a fundamental algorithmic move: change the question to expose shared work.

Go implementation notes

Pointer receiver vs value receiver

Both can work when the struct holds a pointer root:

type Trie struct { root *node }

But pointer receivers are clearer for mutating methods:

func (t *Trie) Insert(word string)

Byte indexing vs rune iteration

For lowercase English constraints:

idx := word[i] - 'a'

This is correct and fast.

For Unicode:

for _, r := range word { ... }

Then use map[rune]*node, not [26]*node.

Avoid substring allocation in recursion

Prefer this:

func dfs(node *node, word string, i int) bool

Over this:

func dfs(node *node, suffix string) bool

Passing word[1:] repeatedly can create unnecessary overhead and makes reasoning less clean.

Do not hide invariants behind cleverness

A clean trie solution is usually short. The hard part is choosing the right invariant and node fields. Keep the code boring.

Testing strategy

A good trie test suite should cover these categories.

Core trie

insert single word
search existing exact word
search prefix that is not a word
startsWith existing prefix
insert prefix after longer word
shared prefix branches
unrelated missing branch
duplicate insert

Wildcard dictionary

exact match
missing exact match
wildcard at start
wildcard at middle
wildcard at end
all wildcard
length mismatch
prefix should not match full word

Word Search II

sample board
single-cell board
duplicate words in input
same word findable through multiple paths
cannot reuse cell
no words found
shared prefixes in word list

Replace Words

basic replacement
overlapping roots choose shortest
no replacement
word equal to root
multiple sentence words
large shared dictionary prefix

Common misconception checklist

Before moving on, a learner should be able to answer these.

1. Does every trie node represent a word? No. It represents a prefix.
2. Does Search(prefix) return true when StartsWith(prefix) is true? Not necessarily.
3. Is a trie always faster than a hash set? No. For exact lookup only, hash set is often better.
4. Does wildcard search always visit every node? No. It visits only states compatible with the pattern.
5. Is Word Search II just backtracking? No. It is backtracking plus prefix pruning.
6. Does clearing word in Word Search II break other words? No, because it clears only the terminal output marker, not the path.
7. Can tries store things other than letters? Yes. Bits, path segments, tokens, bytes, and more.

Interview answer templates

Implement Trie

“I maintain the invariant that each node represents the prefix spelled by the path from the root. Insertion creates missing nodes along the word and marks the final node terminal. Search walks the same path and additionally checks the terminal flag. StartsWith only checks that the path exists. Each operation is linear in the input length.”

Wildcard Word Dictionary

“I use a trie for inserted words. For search, the recursive state is (node, index). A normal letter follows one child. A dot branches over every non-nil child. When the index reaches the pattern length, I return whether the current node is terminal, so prefixes do not incorrectly match full words.”

Word Search II

“I build a trie from all words, then run board DFS from every cell. The current board path must correspond to a trie prefix; if the matching child is missing, I stop immediately. Terminal trie nodes store the full word so I can append it without reconstructing the path. I mark board cells as visited during one DFS path and restore them afterward.”

Replace Words

“I insert dictionary roots into a trie. For each sentence word, I walk character by character. The first terminal trie node on that path is the shortest root because path length increases one character at a time. If no terminal node is reached before a missing edge, I keep the word unchanged.”

Capstone project: mini autocomplete and word-search engine

Build a small command-line program with two modes.

Mode 1: Dictionary service

Commands:

ADD word
EXISTS word
PREFIX prefix
COUNT_PREFIX prefix
DELETE word
SUGGEST prefix k

Requirements:

• Supports duplicates for COUNT operations.
• Deletion should not break shared prefixes.
• SUGGEST returns lexicographically smallest k completions.

Mode 2: Board search

Input:

board dimensions
board rows
dictionary words

Output:

all words found on the board

Requirements:

• No duplicate outputs.
• A cell cannot be reused in one word.
• Must use trie pruning.

What this project proves

If a learner can build this without copying, they understand tries at a professional level:

• Core operations.
• Counts.
• Deletion.
• DFS branching.
• Backtracking integration.
• Output control.
• Practical testing.

Final mental model

A trie is not “a tree of letters.” That description is too shallow.

A trie is a state machine for prefixes.

Each node answers:

What prefix have we consumed so far?
Is that prefix a complete item?
What characters can legally come next?
What metadata does this prefix need to answer the problem quickly?

Once learners see that, trie problems become design problems rather than memorization problems.