Trie Module Slides

These slides are written as teaching slides, not marketing slides. Each slide has a sharp point, a small example, and a speaker note.

Slide 1 — Trie / Prefix Tree

A trie stores strings by sharing prefixes.

app, apple, apply

All share the path:

a -> p -> p

Speaker note: Start with the reason tries exist: many strings share prefixes, and many problems ask about unfinished strings.

Slide 2 — The problem with a hash set

Hash set answers:

Is "apple" present?

It does not naturally answer:

Does anything start with "app"?
What completions exist under "app"?
Can this board path still become a word?

Speaker note: Do not attack hash sets. They are better for exact lookup. Tries are for prefix-shaped work.

Slide 3 — Root means empty prefix

root = ""
root -> a = "a"
root -> a -> p = "ap"
root -> a -> p -> p = "app"

Speaker note: Learners must stop thinking that nodes are “letters only.” Nodes are prefix states.

Slide 4 — The invariant

For every node:

path(root, node) = prefix represented by node
isWord = true means that prefix is a complete inserted word

Speaker note: Every later proof is just this invariant repeated in a new context.

Slide 5 — Prefix is not word

After inserting:

apple

Then:

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

Speaker note: This is the first bug to kill.

Slide 6 — Node shape for lowercase words

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

Speaker note: Fixed arrays are fast and simple under a-z constraints.

Slide 7 — Insert

Insert("cat")
root -> c -> a -> t
mark t as terminal

Speaker note: Insert creates missing edges and reuses existing ones.

Slide 8 — Search

Search("cat")
walk c, a, t
return final.isWord

Speaker note: Existence of path alone is not enough.

Slide 9 — StartsWith

StartsWith("ca")
walk c, a
return path exists

Speaker note: Same walk as search, no terminal check.

Slide 10 — Core trie code structure

func (t *Trie) find(s string) *node
func (t *Trie) Search(s string) bool
func (t *Trie) StartsWith(s string) bool

Speaker note: The helper makes the distinction obvious.

Slide 11 — Complexity

For length L:

Insert:     O(L)
Search:     O(L)
StartsWith: O(L)

Speaker note: Mention memory constants. [26]*node is not free.

Slide 12 — When not to use a trie

Do not default to trie when:

only exact lookup is needed
updates are rare and sorted array is enough
substring search is required
memory is very tight

Speaker note: Professional skill includes rejecting the data structure.

Slide 13 — Wildcard search changes the walk

Pattern:

.ad

. can mean:

a or b or c or ...

Speaker note: A normal character follows one edge. A wildcard branches.

Slide 14 — Wildcard DFS state

(node, indexInPattern)

Base case:

index == len(pattern) -> node.isWord

Speaker note: The base case prevents prefix false positives.

Slide 15 — Wildcard recurrence

letter: follow one child
'.': try all non-nil children

Speaker note: This is controlled branching, not magic.

Slide 16 — Trace .ad

Words:

bad, dad, mad

Search:

. -> try b -> a -> d -> terminal -> true

Speaker note: Search can stop after first successful branch.

Slide 17 — Wildcard complexity

No wildcard: O(L)
Many wildcards: visits many trie states

Speaker note: Say “states visited,” not only 26^L.

Slide 18 — Shortest root replacement

Dictionary:

cat, cattle

Word:

cattleman

First terminal is:

cat

Speaker note: The first terminal on the path is the shortest root.

Slide 19 — Replace words trace

battery -> b -> a -> t [terminal]
replace with "bat"

Speaker note: Stop early. Do not search for longer roots.

Slide 20 — Grid search problem

Board:

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

Words:

oath, pea, eat, rain

Speaker note: Separate DFS per word repeats work.

Slide 21 — Trie as pruning engine

During board DFS, ask:

Is current path a prefix of any target word?

If no, stop.

Speaker note: This is the central aha moment.

Slide 22 — Board DFS state

(row, col, trieNode)

The board path must match a trie path.

Speaker note: Do not carry all words; carry the current trie node.

Slide 23 — Visited cells

mark board[r][c] = '#'
explore neighbors
restore original character

Speaker note: This is standard backtracking.

Slide 24 — Store word at terminal

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

Speaker note: Storing the full word avoids reconstructing the path.

Slide 25 — Avoid duplicates

if node.word != "" {
    result = append(result, node.word)
    node.word = ""
}

Speaker note: Clearing output marker is not deleting the path.

Slide 26 — Word Search II complexity

Build trie:

O(total word length)

DFS:

number of board paths that are also dictionary prefixes

Speaker note: This is more meaningful than only 4^L.

Slide 27 — Counts and deletion

Use counts when duplicates or deletion matter:

countPrefix int
countWord int

Speaker note: isWord cannot count duplicates.

Slide 28 — Delete safely

To erase app from:

app, apple

Do not delete the shared path used by apple.

Speaker note: Counts protect shared prefixes.

Slide 29 — Autocomplete

Two designs:

walk prefix, DFS subtree
cache top-K at every node

Speaker note: Teach the tradeoff, not one “right” answer.

Slide 30 — Bitwise trie

Alphabet can be bits:

0, 1

Use for maximum XOR.

Speaker note: This expands the learner’s idea of trie beyond words.

Slide 31 — Design checklist

Ask:

Alphabet?
Terminal metadata?
Duplicates?
Deletion?
All matches or top-K?
What can be pruned?

Speaker note: This is the practical interview workflow.

Slide 32 — Common bugs

prefix treated as word
nil root
wrong base case in DFS
not restoring board cell
duplicate outputs
wrong alphabet assumption

Speaker note: Convert this into a live debugging checklist.

Slide 33 — Mastery target

A learner is ready when they can build:

ADD / SEARCH / PREFIX / DELETE / SUGGEST
WORD_SEARCH_BOARD

Speaker note: The capstone forces all core ideas together.

Slide 34 — Final model

A trie is a state machine for prefixes.

Each node answers:

What prefix have we consumed?
Is it complete?
What can come next?
What metadata do we need here?

Speaker note: End with the abstraction, not the code.