161. Implement Trie (Prefix Tree)

🔗 LeetCode Problem: 208. Implement Trie (Prefix Tree)
📊 Difficulty: Medium
🏷️ Topics: Trie, String, Design, Hash Table

Problem Statement

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints: - 1 <= word.length, prefix.length <= 2000 - word and prefix consist only of lowercase English letters - At most 3 * 10^4 calls in total will be made to insert, search, and startsWith

---

🌳 Visual Understanding - From Trees to Tries

You Just Mastered Binary Trees!

BINARY TREE (What you know):
       5
      / \
     3   7
    / \
   1   4

Properties:
  - Each node: stores a VALUE
  - Children: LEFT and RIGHT (2 children max)
  - Edges: Relationships (less than, greater than)
  - Use: General hierarchical data
  - Search: O(log n) to O(n)

TRIE (What you're learning):
       root (empty)
      /  |  \
     a   b   c
     |   |   |
     p   a   a
     |   |   |
    p*  t*  t*

Properties:
  - Each node: stores LINKS to children (no value!)
  - Children: 26 possible (one per letter a-z)
  - Edges: CHARACTERS (labeled with letters)
  - Use: STRING operations, prefix matching
  - Search: O(m) where m = key length

Similar structure, different purpose! 🎯

The Core Concept:

A Trie is a TREE where:
  - Each PATH from root to node = a STRING
  - Each EDGE = a CHARACTER
  - Nodes marked with * = END OF WORD

Example: Store ["cat", "car", "dog"]

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

Reading paths:
  root → c → a → t = "cat" ✓
  root → c → a → r = "car" ✓
  root → d → o → g = "dog" ✓

Notice: "cat" and "car" share prefix "ca"!
Shared prefixes share nodes! 🔑

Why Tries are Powerful:

PROBLEM: Store 1000 words, search for prefix "app"

APPROACH 1: ArrayList<String>
  for (String word : list) {
      if (word.startsWith("app")) {
          // found
      }
  }
  Time: O(n * m) where n=words, m=avg length
  Must check ALL 1000 words!

APPROACH 2: HashSet<String>
  // Can't do prefix search efficiently!
  // Would still need to check all entries
  Time: O(n * m) for prefix operations

APPROACH 3: Trie
  Follow path: root → a → p → p
  All words with prefix found!
  Time: O(m) where m=prefix length

1000x faster for prefix operations! ✨

Trie = O(m) for ANY prefix operation!

Real-World Applications:

1. AUTOCOMPLETE:
   Type "hel" → Trie finds: "hello", "help", "helmet"
   Google search, IDE suggestions

2. SPELL CHECKER:
   Type "teh" → Trie suggests: "the", "tea", "ten"
   Word processors, browsers

3. IP ROUTING:
   Match longest prefix for routing
   Network routers use Tries!

4. T9 PREDICTIVE TEXT:
   Phone keyboards (2=abc, 3=def, etc.)
   Press "4663" → Trie suggests: "good", "home"

5. WORD GAMES:
   Boggle, Scrabble word validation
   Check if path is valid word

Tries are EVERYWHERE! 🌐

---

🏗️ TrieNode Structure - Building Blocks

The TrieNode Design:

Each node needs to store TWO things:
  1. Links to children (for 26 letters)
  2. Flag: Is this the end of a word?

TWO implementation options:
  Option 1: Array (26 slots) ← Standard for lowercase English
  Option 2: HashMap (dynamic)

Let's explore both in detail! 🔍

Option 1: Array Implementation (Recommended)

class TrieNode {
    TrieNode[] children;    // 26 slots for 'a' to 'z'
    boolean isEndOfWord;    // True if word ends here

    public TrieNode() {
        children = new TrieNode[26];  // All null initially
        isEndOfWord = false;
    }
}

Visual Representation:

Single TrieNode structure:

┌─────────────────────────────────────────┐
│         TrieNode                        │
├─────────────────────────────────────────┤
│                                         │
│  children array (size 26):              │
│  ┌───┬───┬───┬───┬───┬─────┬───┐      │
│  │ a │ b │ c │ d │ e │ ... │ z │      │
│  ├───┼───┼───┼───┼───┼─────┼───┤      │
│  │ ● │null│●│null│null│...│null│      │
│  └─┼─┴───┴─┼─┴───┴───┴─────┴───┘      │
│    │       │                            │
│    │       └─→ TrieNode (for 'c')      │
│    │                                    │
│    └─→ TrieNode (for 'a')              │
│                                         │
│  isEndOfWord: false                    │
│                                         │
└─────────────────────────────────────────┘

How to access:
  To get child for 'a': children[0]
  To get child for 'b': children[1]
  To get child for 'z': children[25]

Formula: index = character - 'a'
  'a' - 'a' = 0 → children[0]
  'b' - 'a' = 1 → children[1]
  'z' - 'a' = 25 → children[25]

This is THE KEY formula! 🔑

Option 2: HashMap Implementation

class TrieNode {
    Map<Character, TrieNode> children;  // Only stores existing letters
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

Visual Representation:

Single TrieNode with HashMap:

┌─────────────────────────────────────────┐
│         TrieNode                        │
├─────────────────────────────────────────┤
│                                         │
│  children HashMap:                      │
│  ┌────────────────────────┐            │
│  │ 'a' → TrieNode ────────┼──→ •      │
│  ├────────────────────────┤            │
│  │ 'c' → TrieNode ────────┼──→ •      │
│  └────────────────────────┘            │
│  (only 2 entries, not 26!)             │
│                                         │
│  isEndOfWord: false                    │
│                                         │
└─────────────────────────────────────────┘

How to access:
  To get child for 'a': children.get('a')
  To add child for 'b': children.put('b', new TrieNode())
  To check if 'c' exists: children.containsKey('c')

Array vs HashMap - Detailed Comparison:

┌─────────────────────────────────────────────────────────┐
│                    ARRAY vs HASHMAP                     │
├─────────────────────────────────────────────────────────┤
│ CRITERION      │ ARRAY [26]        │ HASHMAP            │
├────────────────┼───────────────────┼────────────────────┤
│ Access Time    │ O(1) guaranteed   │ O(1) average       │
│ Insert Time    │ O(1) guaranteed   │ O(1) average       │
│ Space per Node │ 26 * 8 = 208 bytes│ 16 + entries*24    │
│ Sparse Tries   │ Wasteful ✗       │ Efficient ✓        │
│ Dense Tries    │ Efficient ✓      │ More overhead ✗    │
│ Code Simplicity│ Simpler ✓        │ Slightly complex   │
│ Null Checks    │ More frequent     │ containsKey()      │
│ Cache Locality │ Better ✓         │ Scattered ✗        │
└────────────────┴───────────────────┴────────────────────┘

WHEN TO USE ARRAY:
  ✓ Small alphabet (26 letters)
  ✓ Dense tries (many words, shared prefixes)
  ✓ Performance critical
  ✓ Lowercase English only
  → This is the STANDARD choice! ✓

WHEN TO USE HASHMAP:
  ✓ Large alphabet (Unicode, symbols)
  ✓ Sparse tries (few words, little sharing)
  ✓ Memory constrained
  ✓ Variable character sets
  → Use for special cases

For this problem (lowercase a-z): USE ARRAY! 🎯

Example Comparison:

Insert "a", "ab", "abc" into Trie:

ARRAY VERSION:
  root.children[0] = node_a (25 other nulls)
  node_a.children[1] = node_b (25 other nulls)
  node_b.children[2] = node_c (25 other nulls)

  Total: 3 nodes * 26 * 8 bytes = 624 bytes

HASHMAP VERSION:
  root.children = {'a': node_a}
  node_a.children = {'b': node_b}
  node_b.children = {'c': node_c}

  Total: 3 HashMaps with 1 entry each = ~150 bytes

HashMap wins for sparse!

Insert all words starting with a-z:

ARRAY VERSION:
  root.children[0-25] all filled
  Fixed 208 bytes regardless

HASHMAP VERSION:
  root.children = 26 entries
  HashMap overhead + 26 entries = ~650 bytes

Array wins for dense!

Conclusion: Array is standard for English! ✓

---

🎯 Solution: Trie with Array Implementation

Complete Implementation:

class Trie {
    // Inner class for TrieNode
    private class TrieNode {
        TrieNode[] children;
        boolean isEndOfWord;

        public TrieNode() {
            children = new TrieNode[26];  // One slot per letter
            isEndOfWord = false;
        }
    }

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode current = root;

        // Process each character in the word
        for (char ch : word.toCharArray()) {
            // Convert character to index (0-25)
            int index = ch - 'a';

            // If path doesn't exist, create it
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }

            // Move to next node
            current = current.children[index];
        }

        // Mark the end of the word
        current.isEndOfWord = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        // Word exists if we reach a node AND it's marked as end of word
        return node != null && node.isEndOfWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        // Prefix exists if we can follow the path
        return searchPrefix(prefix) != null;
    }

    /** Helper method to navigate to the end of prefix/word */
    private TrieNode searchPrefix(String prefix) {
        TrieNode current = root;

        // Follow the path character by character
        for (char ch : prefix.toCharArray()) {
            int index = ch - 'a';

            // If path doesn't exist, prefix/word not found
            if (current.children[index] == null) {
                return null;
            }

            // Move to next node
            current = current.children[index];
        }

        // Return the final node we reached
        // (Could be end of word or just a prefix)
        return current;
    }
}

---

🔍 Detailed Dry Run - Building the Trie

Operations sequence:
1. insert("cat")
2. insert("car")
3. insert("dog")
4. search("cat")   → true
5. search("ca")    → false
6. startsWith("ca")→ true
7. search("dog")   → true

Operation 1: insert("cat")

═══════════════════════════════════════════════════
INSERT "cat"
═══════════════════════════════════════════════════

INITIAL STATE:
        root
    (all 26 children = null)

STEP 1: Process 'c'
────────────────────────────────────────────────────
├─ current = root
├─ ch = 'c'
├─ index = 'c' - 'a' = 2
├─ children[2] == null? YES
├─ Create: children[2] = new TrieNode()
└─ Move: current = children[2]

STATE:
        root
         │
      [2]│ (index 2 = 'c')
         ↓
         c
    (26 children, all null)

STEP 2: Process 'a'
────────────────────────────────────────────────────
├─ current = node for 'c'
├─ ch = 'a'
├─ index = 'a' - 'a' = 0
├─ children[0] == null? YES
├─ Create: children[0] = new TrieNode()
└─ Move: current = children[0]

STATE:
        root
         │
         c
         │
      [0]│ (index 0 = 'a')
         ↓
         a
    (26 children, all null)

STEP 3: Process 't'
────────────────────────────────────────────────────
├─ current = node for 'a'
├─ ch = 't'
├─ index = 't' - 'a' = 19
├─ children[19] == null? YES
├─ Create: children[19] = new TrieNode()
└─ Move: current = children[19]

STATE:
        root
         │
         c
         │
         a
         │
     [19]│ (index 19 = 't')
         ↓
         t
    (26 children, all null)

STEP 4: Mark end of word
────────────────────────────────────────────────────
├─ current = node for 't'
├─ Set: current.isEndOfWord = true
└─ Done!

FINAL STATE:
        root
         │
         c
         │
         a
         │
        t* ← isEndOfWord = true

Word "cat" successfully inserted! ✓

═══════════════════════════════════════════════════

Operation 2: insert("car")

═══════════════════════════════════════════════════
INSERT "car" (shares prefix "ca" with "cat")
═══════════════════════════════════════════════════

STEP 1: Process 'c'
────────────────────────────────────────────────────
├─ current = root
├─ index = 2 ('c')
├─ children[2] exists? YES (from "cat") ✓
├─ NO new node created!
└─ Move: current = children[2]

        root
         │
         c ← REUSE existing node!
         │
         a
         │
        t*

STEP 2: Process 'a'
────────────────────────────────────────────────────
├─ current = node for 'c'
├─ index = 0 ('a')
├─ children[0] exists? YES (from "cat") ✓
├─ NO new node created!
└─ Move: current = children[0]

        root
         │
         c
         │
         a ← REUSE existing node!
         │
        t*

STEP 3: Process 'r'
────────────────────────────────────────────────────
├─ current = node for 'a'
├─ index = 17 ('r')
├─ children[17] exists? NO
├─ Create: children[17] = new TrieNode()
└─ Move: current = children[17]

        root
         │
         c
         │
         a
        / \
   [19]│   │[17] (new branch!)
       ↓   ↓
       t*  r

STEP 4: Mark end
────────────────────────────────────────────────────
├─ Set: current.isEndOfWord = true
└─ Done!

FINAL STATE:
        root
         │
         c
         │
         a
        / \
       t*  r* ← Both marked as word endings!

Words "cat" and "car" share prefix "ca"! ✨

═══════════════════════════════════════════════════
Prefix sharing = space efficiency! 🔑
═══════════════════════════════════════════════════

Operation 3: insert("dog")

═══════════════════════════════════════════════════
INSERT "dog" (no shared prefix)
═══════════════════════════════════════════════════

STEP 1-3: Process 'd', 'o', 'g'
────────────────────────────────────────────────────
├─ All new nodes (no overlap with "cat"/"car")
├─ Create: root → d → o → g
└─ Mark: g as end of word

FINAL STATE:
        root
       /    \
   [2]│      │[3]
      ↓      ↓
      c      d
      │      │
      a      o
     / \     │
    t*  r*   g*

Three words stored: "cat", "car", "dog" ✓

═══════════════════════════════════════════════════

Operation 4: search("cat")

═══════════════════════════════════════════════════
SEARCH "cat" (looking for exact word)
═══════════════════════════════════════════════════

STEP 1: Process 'c'
────────────────────────────────────────────────────
├─ current = root
├─ index = 2
├─ children[2] exists? YES ✓
└─ Move: current = children[2]

STEP 2: Process 'a'
────────────────────────────────────────────────────
├─ current = node for 'c'
├─ index = 0
├─ children[0] exists? YES ✓
└─ Move: current = children[0]

STEP 3: Process 't'
────────────────────────────────────────────────────
├─ current = node for 'a'
├─ index = 19
├─ children[19] exists? YES ✓
└─ Move: current = children[19]

STEP 4: Check if this is end of word
────────────────────────────────────────────────────
├─ Reached node? YES ✓
├─ node.isEndOfWord? YES ✓
└─ return true

        root
         │
         c
         │
         a
        / \
       t* ← Found! isEndOfWord = true

Result: true (word "cat" exists!) ✓

═══════════════════════════════════════════════════

Operation 5: search("ca")

═══════════════════════════════════════════════════
SEARCH "ca" (looking for exact word)
═══════════════════════════════════════════════════

STEP 1-2: Process 'c', 'a'
────────────────────────────────────────────────────
├─ Successfully navigate: root → c → a
└─ Reached node for 'a'

STEP 3: Check if this is end of word
────────────────────────────────────────────────────
├─ Reached node? YES ✓
├─ node.isEndOfWord? NO ✗
└─ return false

        root
         │
         c
         │
         a ← Here, but isEndOfWord = false!
        / \
       t*  r*

Result: false ("ca" is a prefix, not a word!) ✗

This is the KEY difference from startsWith! 🔑

═══════════════════════════════════════════════════

Operation 6: startsWith("ca")

═══════════════════════════════════════════════════
STARTS_WITH "ca" (looking for prefix)
═══════════════════════════════════════════════════

STEP 1-2: Process 'c', 'a'
────────────────────────────────────────────────────
├─ Successfully navigate: root → c → a
└─ Reached node for 'a'

STEP 3: Check if we reached a valid node
────────────────────────────────────────────────────
├─ Reached node? YES ✓
├─ Check isEndOfWord? NO (don't care!)
└─ return true

        root
         │
         c
         │
         a ← Path exists!
        / \
       t*  r* ← Words exist with this prefix!

Result: true (prefix "ca" exists!) ✓

Difference between search and startsWith:
  search("ca"):      false (needs isEndOfWord = true)
  startsWith("ca"):  true  (just needs path to exist)

═══════════════════════════════════════════════════

Operation 7: search("dog")

═══════════════════════════════════════════════════
SEARCH "dog"
═══════════════════════════════════════════════════

STEP 1-3: Navigate d → o → g
────────────────────────────────────────────────────
├─ All nodes exist ✓
└─ Reached node 'g'

STEP 4: Check end of word
────────────────────────────────────────────────────
├─ node.isEndOfWord? YES ✓
└─ return true

        root
       /    \
      c      d
      │      │
      a      o
     / \     │
    t*  r*   g* ← Found!

Result: true ✓

═══════════════════════════════════════════════════

---

📊 Complexity Analysis

Time Complexity:

Let m = length of word/prefix
Let n = total number of words inserted
Let ALPHABET_SIZE = 26

insert(word):
  - Iterate through m characters: O(m)
  - Each iteration: 
      - Compute index: O(1)
      - Check/create child: O(1)
      - Move pointer: O(1)
  - Total: O(m)

search(word):
  - Iterate through m characters: O(m)
  - Each iteration: O(1) operations
  - Total: O(m)

startsWith(prefix):
  - Same as search
  - Total: O(m)

KEY INSIGHT: Time is INDEPENDENT of n!
  Whether we have 10 words or 10,000 words,
  search time is ONLY dependent on word length! ✨

Compare with alternatives:
  ArrayList: O(n * m) for search
  HashSet: O(m) for exact match, O(n * m) for prefix
  Trie: O(m) for EVERYTHING! 🏆

Space Complexity:

Per TrieNode:
  - children array: 26 pointers = 26 * 8 bytes = 208 bytes
  - isEndOfWord: 1 byte
  - Total per node: ~209 bytes

Worst case (no prefix sharing):
  Every word has unique path
  n words, average length m
  Total nodes: O(n * m)
  Total space: O(ALPHABET_SIZE * n * m)

  Example: 100 words, avg length 5
    Nodes: 100 * 5 = 500 nodes
    Space: 500 * 209 bytes ≈ 104.5 KB

Best case (maximum prefix sharing):
  All words share common prefix
  Total nodes: O(m_longest)

  Example: ["a", "aa", "aaa", "aaaa"]
    Nodes: 4 (not 4 * average length!)
    All words share single path!

Real-world case:
  English dictionary (~170,000 words)
  Average prefix sharing
  Actual space: ~3-5 MB for full dictionary

  Much better than storing strings individually:
    170,000 * 10 chars * 2 bytes = 3.4 MB
  And we get O(m) operations! ✨

Space-time tradeoff:
  Use more space → Get faster prefix operations
  Classic engineering tradeoff! 🎯

Comparison Table:

┌──────────────────────────────────────────────────────────┐
│           OPERATIONS COMPARISON                          │
├──────────────┬─────────────┬────────────┬──────────────┤
│ OPERATION    │ TRIE        │ HASHSET    │ ARRAYLIST    │
├──────────────┼─────────────┼────────────┼──────────────┤
│ Insert       │ O(m)        │ O(m)       │ O(1)         │
│ Search Word  │ O(m)        │ O(m)       │ O(n*m)       │
│ Prefix Search│ O(m) ✨     │ O(n*m)     │ O(n*m)       │
│ Delete       │ O(m)        │ O(m)       │ O(n*m)       │
│ Space        │ O(26*n*m)   │ O(n*m)     │ O(n*m)       │
├──────────────┼─────────────┼────────────┼──────────────┤
│ Best For     │ Prefix ops! │ Exact match│ Small n      │
└──────────────┴─────────────┴────────────┴──────────────┘

Trie excels at prefix operations! 🏆

---

⚠️ Common Mistakes

Mistake 1: Forgetting to Mark End of Word

// ❌ WRONG - Inserting without marking end
public void insert(String word) {
    TrieNode current = root;
    for (char ch : word.toCharArray()) {
        int index = ch - 'a';
        if (current.children[index] == null) {
            current.children[index] = new TrieNode();
        }
        current = current.children[index];
    }
    // MISSING: current.isEndOfWord = true;
}

// Problem: search() will return false even for inserted words!

Example:
  insert("cat")
  insert("catch")

  Trie structure:
        root
         │
         c
         │
         a
         │
         t ← NOT marked! ✗
         │
         c
         │
         h* ← Only this marked

  search("cat"): 
    - Reaches node 't'
    - isEndOfWord? false
    - Returns false ✗ (WRONG! We inserted "cat"!)

// ✓ CORRECT - Always mark end
current.isEndOfWord = true;

Mistake 2: Wrong Index Calculation

// ❌ WRONG - Using character directly as index
int index = ch;  // 'a' = 97 in ASCII!

children[97];  // ArrayIndexOutOfBoundsException!
// Array only has 26 slots (0-25)!

// ❌ ALSO WRONG - Hardcoding ASCII values
int index = ch - 97;  // What if uppercase? What if Unicode?

// ✓ CORRECT - Subtract 'a' character
int index = ch - 'a';  
// 'a' - 'a' = 0
// 'b' - 'a' = 1
// 'z' - 'a' = 25

Why this works:
  Java guarantees 'a' to 'z' are consecutive in order
  Subtracting 'a' gives perfect 0-25 range! ✓

Mistake 3: Not Checking Null Before Access

// ❌ WRONG - Accessing without null check
public boolean search(String word) {
    TrieNode current = root;
    for (char ch : word.toCharArray()) {
        int index = ch - 'a';
        current = current.children[index];  // NullPointerException!
    }
    return current.isEndOfWord;
}

// Problem: If path doesn't exist, current becomes null!

Example:
  Trie only has "cat"
  search("dog"):
    - Process 'd': children[3] is null
    - current = null
    - Next iteration: null.children[...] → CRASH! ✗

// ✓ CORRECT - Check before accessing
if (current.children[index] == null) {
    return false;  // Path doesn't exist
}
current = current.children[index];

Mistake 4: Confusing search() and startsWith()

// Common confusion about the difference!

// ❌ WRONG - Using same logic for both
public boolean search(String word) {
    TrieNode node = find(word);
    return node != null;  // WRONG for search!
}

public boolean startsWith(String prefix) {
    TrieNode node = find(prefix);
    return node != null;  // Correct for startsWith!
}

// Problem: search() should check isEndOfWord!

Example:
  Trie has "apple"
  search("app"):
    - Path exists (a → p → p)
    - But "app" wasn't inserted!
    - Should return false!

// ✓ CORRECT - Different checks
public boolean search(String word) {
    TrieNode node = find(word);
    return node != null && node.isEndOfWord;  ✓
    // Must be marked as word!
}

public boolean startsWith(String prefix) {
    TrieNode node = find(prefix);
    return node != null;  ✓
    // Just needs path to exist!
}

KEY DIFFERENCE:
  search:      Exact word must be inserted
  startsWith:  Any word with this prefix counts

Mistake 5: Using Wrong Data Structure for Children

// ❌ WRONG - List instead of array
List<TrieNode> children = new ArrayList<>();

// Problem: How to map 'a' to index 0?
// List doesn't support direct indexed access by character!

// ❌ WRONG - HashMap with String keys
Map<String, TrieNode> children = new HashMap<>();

// Problem: Keys should be Character, not String!
children.put("a", node);  // WRONG!
children.put('a', node);  // ✓ Correct

// ✓ CORRECT - Array for lowercase English
TrieNode[] children = new TrieNode[26];

// ✓ ALSO CORRECT - HashMap with Character
Map<Character, TrieNode> children = new HashMap<>();

Choose based on requirements:
  - Fixed alphabet (a-z): Array
  - Variable alphabet: HashMap

Mistake 6: Off-by-One in Array Size

// ❌ WRONG - Array size 25
TrieNode[] children = new TrieNode[25];  // WRONG!

// Problem: 'z' - 'a' = 25, needs index 25!
// Array with size 25 has indices 0-24 only!
// Accessing children[25] → ArrayIndexOutOfBoundsException!

// ✓ CORRECT - Array size 26
TrieNode[] children = new TrieNode[26];  // 0-25 ✓

Remember: 26 letters, need indices 0-25, size must be 26!

---

🎯 Pattern Recognition - Trie Applications

Core Pattern: Prefix-Based String Operations

Template for Trie problems:

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
    // Additional fields as needed (frequency, data, etc.)
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (curr.children[i] == null) {
                curr.children[i] = new TrieNode();
            }
            curr = curr.children[i];
        }
        curr.isEndOfWord = true;
    }

    // Variations: search, prefix, pattern matching, etc.
}

This is your BASE template! Modify as needed! 🎯

Related LeetCode Problems:

1. Add and Search Word - Data structure design (211)

Trie + Wildcard matching
- Handle '.' as any character
- DFS to try all possible paths
- Similar to basic Trie but with backtracking

Difficulty: Medium
Pattern: Trie + DFS

2. Word Search II (212)

Trie + Backtracking on 2D grid
- Build trie of target words
- Search grid using trie for pruning
- Much faster than searching each word separately

Difficulty: Hard
Pattern: Trie + Grid DFS + Backtracking
Key: Trie eliminates invalid paths early!

3. Implement Magic Dictionary (676)

Trie + One character difference
- Search with exactly one mismatch allowed
- Try changing each position
- Use Trie to check if resulting word exists

Difficulty: Medium
Pattern: Trie + Modified search

4. Design Search Autocomplete System (642)

Trie + Frequency tracking + Top-K
- Store frequency count in nodes
- Return top k frequent suggestions
- Real autocomplete implementation!

Difficulty: Hard
Pattern: Trie + Heap + Sorting

5. Replace Words (648)

Trie for dictionary, find shortest root
- Build trie of roots
- For each word, find shortest matching root
- String replacement problem

Difficulty: Medium
Pattern: Trie + String manipulation

6. Longest Word in Dictionary (720)

Trie with build-up validation
- Word valid if all prefixes exist
- Find longest valid word
- Lexicographically smallest if tie

Difficulty: Medium
Pattern: Trie + DFS traversal

7. Map Sum Pairs (677)

Trie with value storage
- Store values at nodes
- Sum all values on prefix path
- Running sum problem

Difficulty: Medium
Pattern: Trie + Aggregation

When to Recognize Trie Problems:

USE TRIE when you see these keywords:

✓ "prefix"
✓ "autocomplete"
✓ "suggest"
✓ "dictionary"
✓ "spell check"
✓ "word search" (with multiple words)
✓ "longest common prefix"
✓ "phone directory"
✓ "IP routing"
✓ "T9 text input"

Pattern recognition:
  If problem involves MULTIPLE strings and PREFIX operations
  → Think TRIE! 🔑

Alternative data structures comparison:
  - HashMap: Good for exact match, bad for prefix
  - Array: Good if few words, bad for many
  - Trie: Excellent for prefix, worth the space!

---

📝 Quick Revision Notes

🎯 Core Concept

Trie = tree where path represents string, edges are characters. Each node has 26 children (array) for 'a'-'z' plus isEndOfWord flag. Insert/search/prefix all O(m) time where m = word length, independent of number of words stored! Space efficient through prefix sharing. Use for autocomplete, spell check, dictionary, any prefix operations.

⚡ Quick Implementation

class TrieNode {
  TrieNode[] children;
  boolean isEnd;

  public TrieNode() {
    // Just space allocated. All are NULLs.
    // For example, this.children[0] = null, this.children[1] = null and so on till this.children[25] = null
    // Why null? We will initialize with new TrieNode() only when character comes. Why unncessary space before char comes?
    // Check insert method. Only when character comes, we go and initialize that element in the array.
    this.children = new TrieNode[26];
    this.isEnd = false;
  }  
}

class Trie {
  TrieNode root;

  public Trie() {
    root = new TrieNode();
  }

  public void insert(String word) {
    // Get the current root of the tree.    
    TrieNode curr = root;

    for(char ch : word.toCharArray()) {
      int index = ch - 'a';
      if(curr.children[index] == null) {
        curr.children[index] = new TrieNode(); // when you initialize, it is non-null and it means character is present.
      }

      // now move to next char
      curr = curr.children[index];
    }

    // marks the end of the word. Useful to find whether the full word is present there or not instead of pattern/prefix.
    curr.isEnd = true;
  }

  public boolean search(String word) {
    TrieNode curr = root;

    for(char ch : word.toCharArray()) {
      int index = ch - 'a';

      if(curr.children[index] == null) {
        return false;
      }

      curr = curr.children[index];
    }

    return curr != null && curr.isEnd;      
  }

  public boolean startsWith(String prefix) {
    TrieNode curr = root;

    for(char ch : prefix.toCharArray()) {
      int index = ch - 'a';

      if(curr.children[index] == null) {
        return false;
      }

      curr = curr.children[index];
    }

    return true;
  }
}

public class Solution {
    public static void main(String[] args) {
        Trie trie = new Trie();
    trie.insert("apple");
    System.out.println(trie.search("apple")); // true
    System.out.println(trie.search("app")); // false
    System.out.println(trie.startsWith("app")); // true
    trie.insert("app");
    System.out.println(trie.search("app")); // true
    }
}

🔑 Key Insights

Characters on Edges, Not Nodes:

CRITICAL UNDERSTANDING:

        root (no character!)
         │
    edge 'c'
         │
         c (no character stored!)
         │
    edge 'a'
         │
         a
         │
    edge 't'
         │
        t*

Characters label EDGES, not nodes!
Node stores: children array + isEnd flag
Node does NOT store a character value!

This is different from BST where nodes store values! 🔑

The Magic Formula:

index = ch - 'a'

Examples:
  'a' - 'a' = 0   → children[0]
  'b' - 'a' = 1   → children[1]
  'c' - 'a' = 2   → children[2]
  ...
  'z' - 'a' = 25  → children[25]

Works because:
  - 'a' to 'z' are consecutive in ASCII
  - Guaranteed by Java/C++ standards
  - Maps perfectly to 0-25 range

This ONE formula is used EVERYWHERE! ✨

Search vs StartsWith:

THE KEY DIFFERENCE:

search("app"):
  - Follow path: root → a → p → p
  - Reach node for second 'p'
  - Check: isEndOfWord?
  - Return true ONLY if word was inserted!

  Example: Trie has "apple"
    search("app") → false ✗
    (path exists but "app" wasn't inserted)

startsWith("app"):
  - Follow path: root → a → p → p
  - Reach node for second 'p'
  - Don't check isEndOfWord!
  - Return true if path exists!

  Example: Trie has "apple"  
    startsWith("app") → true ✓
    (prefix of "apple")

One line difference, huge semantic difference! 🎯

Prefix Sharing = Space Efficiency:

Words: ["cat", "car", "dog"]

Without sharing (storing strings):
  "cat" → 3 chars
  "car" → 3 chars
  "dog" → 3 chars
  Total: 9 character storage

With Trie (prefix sharing):
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*

  Nodes: 7 total
  "ca" stored once, shared by "cat" and "car"!

Real example - English dictionary:
  170,000 words
  Without sharing: ~1.7 million characters
  With Trie: ~500,000 nodes (3x compression!)

More sharing = more savings! ✨

Time Independent of Word Count:

AMAZING PROPERTY:

insert("hello") takes same time whether:
  - Trie is empty
  - Trie has 10 words
  - Trie has 1,000,000 words

Time: O(5) = O(m) where m = length of "hello"

Compare with ArrayList:
  - search("hello") in list of 1,000,000 words
  - Time: O(1,000,000 * 5) = O(n * m)

Trie is INDEPENDENT of n! 🚀

This is WHY Tries are powerful for large datasets!

🎪 Memory Aid

"Path equals string!"
"Edge has character, node has links!"
"ch - 'a' for index!"
"isEnd marks complete words!"
"O(m) for all operations!" ✨

⚠️ Don't Forget

• Mark isEndOfWord after insert!
• Check null before access (avoid NPE!)
• Index = ch - 'a' (not just ch!)
• search checks isEnd, startsWith doesn't!
• 26 children for lowercase a-z!
• Characters on edges, not in nodes!

---

🎉 Congratulations!

You've mastered the Trie data structure - your first specialized tree!

What You Learned:

✅ Trie structure - Paths represent strings
✅ TrieNode design - Array vs HashMap tradeoffs
✅ Insert operation - Character-by-character building
✅ Search vs Prefix - isEndOfWord distinction
✅ Space sharing - Common prefixes stored once
✅ O(m) operations - Independent of word count
✅ Real applications - Autocomplete, spell check, routing

Transition from Trees to Tries:

Your Binary Tree mastery transferred perfectly!

BINARY TREE → TRIE MAPPING:

Tree Concept          →  Trie Adaptation
──────────────────────────────────────────
Node stores value     →  Node stores links only
2 children (L/R)      →  26 children (a-z)
Value comparison      →  Character matching
General hierarchy     →  String storage
O(log n) to O(n)      →  O(m) always

Same foundation, new application! 🌲→🌳

Skills transferred:
  ✓ Tree traversal → Path following
  ✓ Node structure → TrieNode design
  ✓ Recursion → Iterative building
  ✓ Edge navigation → Character edges

Tree mastery → Trie mastery! 💪

The Power of Tries:

Why Tries are AMAZING:

1. O(m) operations (not O(n)!)
   Fast regardless of dataset size

2. Prefix operations in O(m)
   Autocomplete, suggestions, spell check

3. Space efficient through sharing
   Common prefixes stored once

4. Deterministic performance
   No hash collisions, no worst cases

5. Ordered traversal possible
   DFS gives lexicographically sorted words

6. Deletion friendly
   Can remove words cleanly

Used in PRODUCTION systems:
  - Google Search autocomplete
  - Text editors (VSCode, IntelliJ)
  - Network routers (IP lookup)
  - Phone keyboards (T9)
  - Spell checkers

You just learned a PRODUCTION data structure! 🏆

Interview Mastery:

Interviewer: "Implement a Trie (Prefix Tree)"

Your response:
  "A Trie is a tree where paths represent strings.

   Structure:
   - Each node has 26 children (for 'a'-'z')
   - Characters are on edges, not nodes
   - Nodes have isEndOfWord flag

   TrieNode design choices:
   - Array[26]: O(1) access, standard for English
   - HashMap: Better for sparse, large alphabets

   Operations (all O(m) where m = word length):

   insert(word):
   - Navigate/create path character by character
   - Mark end with isEndOfWord = true

   search(word):
   - Follow path
   - Return true if reach node AND isEndOfWord

   startsWith(prefix):
   - Follow path
   - Return true if path exists (ignore isEndOfWord)

   Key insight: Time is O(m), independent of 
   how many words are stored!

   Space: O(ALPHABET * n * m) worst case,
   but prefix sharing provides efficiency.

   Perfect for autocomplete, spell check,
   and any operation involving prefixes."

Then code it cleanly in 5 minutes! ✓

Shows complete mastery! 💯

What's Next:

With Trie foundation mastered, ready for:

✓ Wildcard matching (Add and Search Word)
✓ Grid + Trie (Word Search II)
✓ Advanced variations (autocomplete, etc.)
✓ Trie optimizations (compressed tries)

You have the foundation! 🚀

You've unlocked a powerful new data structure used in real systems worldwide! Ready for Trie applications! 🏆✨🎯