4.1 Tries

Deep Dive: Trie in Action

Beginner tip: A Trie (pronounced "try") is a tree built from characters. Imagine the autocomplete on your phone: as you type "app", it instantly shows "apple", "application", "appetizer". A Trie stores words letter by letter, sharing common prefixes. Looking up a word takes O(word length) -- no matter how many words are stored.

Insert and Search Traced

Insert "apple", "app", "apt" into empty trie:

Insert "apple":
  root -> a -> p -> p -> l -> e(END)

Insert "app":
  root -> a -> p -> p(END) -> l -> e(END)
  Reuses existing a-p-p path, just marks 'p' as END.

Insert "apt":
  root -> a -> p -> p(END) -> l -> e(END)
                \-> t(END)
  Branches at the second 'p' node.

Final tree:
        root
         |
         a
         |
         p
        / \
       p   t*
       |*
       l
       |
       e*        (* = end of word)

Search vs StartsWith

search("app")  -> walk a-p-p, check is_end=True  -> True
search("ap")   -> walk a-p, check is_end=False   -> False
startsWith("ap") -> walk a-p, node exists         -> True

Word Search II (Trie + Grid DFS)

Build a trie from the word dictionary. DFS from each grid cell. At each step, check if the current path exists in the trie. If the trie node has no children matching the next letter, PRUNE (stop early). This avoids rechecking the dictionary for every path.

---

Before You Start -- How to Think About Tries

Why Tries Exist

Need: Efficient prefix-based search. HashMap can look up "apple" in O(1) but can't answer "what words start with 'app'?" efficiently. Trie: O(length) for insert, search, and prefix search. Shared prefixes = shared nodes = space efficient for dictionaries.

The Mental Model

A Trie is a tree where each edge represents a character.
Path from root to a node = a prefix.
Nodes marked as "end" = complete words.

Words: ["apple", "app", "apt"]

         root
          |
          a
          |
          p
         / \
        p   t    <- "apt" ends here
        |
        l
        |
        e    <- "apple" ends here
        ("app" also ends at the first 'p' after 'a-p')

When to Use a Trie

1. "Find all words with prefix X" -> Trie
2. "Word search in a grid + dictionary" -> Trie + DFS (Word Search II)
3. "Auto-complete" -> Trie
4. "Replace words with shortest prefix" -> Trie
5. Any problem where you're matching against a DICTIONARY of words -> Consider Trie

Implementation Tip

Each node is a dict of {char: TrieNode} with a boolean is_end.

Problems

#	Problem	Status
1	Implement Trie	[ ]
2	Design Add and Search Words	[ ]
3	Word Search II (Trie + DFS)	[ ]
4	Longest Word in Dictionary	[ ]
5	Replace Words	[ ]

Notes