Trie Patterns

Trie = Prefix Tree

Use Trie when we have many strings and need to work with their prefixes efficiently.

Common signals:

prefix
starts with
autocomplete
dictionary
wildcard
word break
XOR

Main idea

Each node represents a prefix.

          root
           |
           c
           |
           a
          / \
         t   r

cat and car share the prefix ca.

---

Pattern Table

Pattern	Question Type	Clues	Main Idea
Basic Trie	Insert / Search	dictionary, word	Store characters
Prefix Search	Prefix / Autocomplete	prefix, starts with	Find prefix, then explore
Wildcard Trie	Pattern matching	., wildcard	Trie + DFS
Trie + DP	Word Break	break, segment	Trie + DP
Bitwise Trie	XOR problems	XOR, bits	Store binary bits

These are the main Trie patterns worth knowing for FAANG-style DSA interviews.

---

1. Basic Trie

Use when

• Insert words
• Search words
• Check if a prefix exists

Example:

insert("cat")
insert("car")

search("cat")      -> true
search("cap")      -> false
startsWith("ca")   -> true

Basic node:

children
isEnd

Trigger

Many words + repeated search
        ↓
      Trie

---

2. Prefix Search / Autocomplete

Use when

• Find words starting with a prefix
• Autocomplete
• Search suggestions
• Longest prefix
• Prefix-based queries

Example:

words:
cat
car
cart
dog

prefix = "ca"

        ca
       /  \
      t    r
           |
           t

Everything below ca starts with ca.

Trigger

"starts with..."
"given prefix..."
"autocomplete..."
        ↓
      Trie

---

3. Wildcard Trie

Use when

Dictionary words need to match a pattern.

Common wildcard:

. = any character

Example:

dictionary:
cat
car
dog

pattern:
c.t

For a normal character:

follow that child

For .:

try all children

So we use:

Trie + DFS / Backtracking

Trigger

Dictionary + wildcard
        ↓
   Trie + DFS

---

4. Trie + DP / DFS

Use when

• Word Break
• String segmentation
• Split string using dictionary words
• Find valid words inside a string

Example:

s = "applepie"

dictionary:
apple
pie

Trie finds:

apple

Then DP checks the remaining:

pie

Think:

Trie = find possible words
DP   = decide if the rest can be formed

Trigger

"break / segment string using dictionary"
        ↓
    Trie + DP

---

5. Bitwise Trie

Use when

• Maximum XOR
• Minimum XOR
• XOR queries

Store numbers as binary instead of characters.

Example:

5 = 101

root
 |
 1
 |
 0
 |
 1

Each node has at most:

0
1

For maximum XOR:

current bit = 0 → prefer 1
current bit = 1 → prefer 0

Process:

MSB → LSB

Trigger

XOR + bits
    ↓
Bitwise Trie

---

How to Recognize Trie Problems

Ask:

1. Are there many strings?
2. Is prefix important?
3. "Starts with"?
4. Autocomplete / suggestions?
5. Wildcard matching?
6. Word Break / segmentation?
7. XOR + binary bits?

If yes, think about Trie.

---

Trie vs Other Structures

Problem	Usually Use
Exact lookup	HashSet / HashMap
Prefix search	Trie
Autocomplete	Trie
Wildcard dictionary	Trie + DFS
Word Break	HashSet + DP / Trie + DP
Maximum XOR	Bitwise Trie
Sorting strings	Array + Sort
Range queries	Segment Tree / Fenwick
Graph traversal	DFS / BFS

---

Complexity

For a word of length L:

Insert       O(L)
Search       O(L)
Prefix check O(L)

If total characters in all words = N:

Build Trie = O(N)
Space       = O(N)

For Bitwise Trie, with B bits:

Insert = O(B)
Query  = O(B)

Usually B = 32 for integers.

---

Trie Master Rules

Root = empty prefix

Node = prefix

Edge = character / bit

isEnd = complete word

Remember:

Prefix      → Trie

Autocomplete
            → Trie

Wildcard    → Trie + DFS

Word Break  → Trie + DP

XOR         → Bitwise Trie