Pattern #20 — Trie (Prefix Tree) 🌲

Pattern #20 — Trie (Prefix Tree) 🌲

A Trie (say it "try") is a special tree designed for one job: storing and searching words super fast, especially by their prefixes. It's what powers autocomplete.

1. The Idea (in one line)

Store words letter by letter in a tree, so shared prefixes share the same path.

   Real-life analogy 🔤
   ────────────────────
   Think of a phone's autocomplete. You type "ca" and it instantly
   suggests "cat", "car", "care". It's not scanning every word in
   the dictionary — it walked down a tree following c → a, and now
   every word underneath starts with "ca". That tree is a Trie.

2. The Picture

   Words stored: "cat", "car", "care", "dog"

              (root)
              /     \
            c        d
            |        |
            a        o
           / \       |
          t*  r      g*
              |
              e*

   * = "a word ends here"

   • "cat", "car", "care" all SHARE the "ca" path → no duplication.
   • Searching a word = walk down letter by letter.
   • Searching a PREFIX = walk down, then everything below matches.

3. What Each Node Looks Like

   Each node has:
   • children: a map from a letter → the next node
   • isEnd: true if a word finishes exactly here

   node = {
     children: { 'a': node, 'b': node, ... },
     isEnd: false
   }

4. 🔍 How to SPOT This Pattern

   Use a Trie when you see:
   ✅ "prefix", "starts with", "autocomplete"
   ✅ "dictionary of words", "word search"
   ✅ "add and search words"
   ✅ Many words, and you'll do MANY prefix lookups
   ✅ "longest common prefix" across many words

5. The Code Template 📝

   class Trie {
     constructor() {
       this.root = { children: {}, isEnd: false };
     }

     insert(word) {
       let node = this.root;
       for (const ch of word) {
         if (!node.children[ch])
           node.children[ch] = { children: {}, isEnd: false };
         node = node.children[ch];      // walk/create the path
       }
       node.isEnd = true;               // mark word end
     }

     search(word) {                     // exact word?
       const node = this._walk(word);
       return node !== null && node.isEnd;
     }

     startsWith(prefix) {               // any word with this prefix?
       return this._walk(prefix) !== null;
     }

     _walk(str) {                       // follow the path, or null
       let node = this.root;
       for (const ch of str) {
         if (!node.children[ch]) return null;
         node = node.children[ch];
       }
       return node;
     }
   }

6. Why Not Just Use a Hash Set of Words?

   A hash set answers "is this EXACT word here?" instantly.
   BUT it CAN'T answer "how many words start with 'ca'?" without
   scanning everything.

   A Trie answers PREFIX questions naturally — that's its whole
   reason to exist. If you need prefixes → Trie. If you only need
   exact-match → a hash set is simpler.

7. Practice Problems

   ⭐ core
   • Implement Trie (Insert / Search / StartsWith)
   • Longest Common Prefix

   ⭐⭐ Medium
   • Design Add and Search Words (with '.' wildcard)
   • Word Search II (Trie + DFS on a grid — a classic combo!)
   • Replace Words
   • Search Suggestions System (autocomplete)

8. ⚠️ Common Mistake

   ❌ Forgetting the `isEnd` flag. Without it you can't tell a
      stored word ("car") from just a prefix on the way to a
      longer word ("care"). The flag marks real word endings.

Key Takeaway

   Trie = a letter-by-letter tree where shared prefixes share a
   path. It makes prefix search ("starts with") fast and natural —
   the engine behind autocomplete and dictionary problems. Use it
   when prefixes matter; use a hash set when only exact match does.

Next: Pattern #21 — Hash Maps, the most-used tool in all of DSA. 🗂️