9.1 Tries (Prefix Trees)

1. What Is a Trie (Prefix Tree)?

A Trie (pronounced "try", from re-trie-val) is a tree where each step down a branch represents one character of a word. Instead of storing whole strings like "cat", "car", and "cart" separately, a Trie shares their common starting letters (root -> 'c' -> 'a') and branches out only where the letters differ!

Each TrieNode holds just two things:

1. children: A dictionary (or 26-slot array for 'a'..'z') mapping the next character to its child TrieNode.
2. is_end: A True/False flag marking whether a complete word finishes at this exact node (for example, so you can tell if "car" was inserted as a full word and not just as the first 3 letters of "cart").

2. Why Do We Need a Trie Instead of a Hash Set?

Suppose you have a dictionary of 500,000 words and want to answer:

1. Autocomplete / Prefix Check (startsWith("app")): "Do ANY words in the dictionary begin with 'app'?"
   • Hash Set: Must scan all 500,000 words (O(N * L)), because hashing scrambles the whole word and loses prefix structure.
   • Trie: Just walk 3 steps from root ('a' -> 'p' -> 'p'). Takes O(L) time (3 steps) regardless of whether the dictionary has 10 words or 10 million words!
2. Board Pruning (Word Search II): While backtracking on a 2D letter grid, if your current path is "qz" and 'q' has no 'z' child in the Trie, you can stop searching that branch immediately!

3. Basic Operations & Walkthroughs (All 4 Languages)

class TrieNode:
  def __init__(self):
      self.children = {}
      self.is_end = False

class Trie:
  def __init__(self):
      self.root = TrieNode()

  # 1. Insert a word character by character -> O(L)
  def insert(self, word: str) -> None:
      curr = self.root
      for ch in word:
          if ch not in curr.children:
              curr.children[ch] = TrieNode()
          curr = curr.children[ch]
      curr.is_end = True

  # 2. Check if an EXACT word exists -> O(L)
  def search(self, word: str) -> bool:
      curr = self.root
      for ch in word:
          if ch not in curr.children:
              return False
          curr = curr.children[ch]
      return curr.is_end

  # 3. Check if ANY word starts with prefix -> O(L)
  def startsWith(self, prefix: str) -> bool:
      curr = self.root
      for ch in prefix:
          if ch not in curr.children:
              return False
          curr = curr.children[ch]
      return True

4. Core Interview Patterns & Common Traps

# Wildcard '.' Search in a Trie (Design Add and Search Words):
def dfs(idx: int, node: TrieNode) -> bool:
  if idx == len(word):
      return node.is_end
  ch = word[idx]
  if ch == ".":
      return any(dfs(idx + 1, child) for child in node.children.values())
  return ch in node.children and dfs(idx + 1, node.children[ch])

5. Practice On Your Own (Curated Submodule Problems)