Trie (Prefix Tree) Complete Guide - Master String Operations in O(m) Time

What is a Trie?

A Trie (pronounced “try”), also known as a Prefix Tree, is a tree-like data structure designed for efficient string operations. Unlike hash tables that store entire keys, a Trie shares common prefixes between strings, making it incredibly space-efficient for dictionary-like data.

Why Interviewers Love Trie

1. Tests deep understanding - You need to grasp tree structures and recursion
2. Elegant prefix operations - startsWith becomes trivially simple
3. Combines with other patterns - Often used with DFS/BFS for complex problems
4. Real-world applications - Autocomplete, spell checkers, IP routing

When to Use Trie vs HashMap

Scenario	Trie	HashMap
Prefix matching	✅ O(m)	❌ O(n×m)
Exact lookup	✅ O(m)	✅ O(m) avg
Space for common prefixes	✅ Shared	❌ Duplicate
Lexicographic ordering	✅ Natural	❌ Extra sort
Memory per node	❌ Array/Map overhead	✅ Minimal

m = word length, n = number of words

---

Core Intuition

The Magic of Shared Prefixes

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

        (root)
       /      \
      a        b
      |        |
      p        a
     /|\       |
    p l t      t
    |  \
    l   y     ← "apply" ends here
    |
    e         ← "apple" ends here

Nodes with ● are end-of-word markers

Key insight: Words sharing the prefix “app” (apple, apply) share the same path from root until they diverge.

---

Interactive Trie Visualizer

Watch how insert, search, and startsWith operations work step-by-step:

Initializing...

---

Implementation Template

Map-based (Flexible Characters)

JavaScriptJavaPython

Loading...

Array-based (Lowercase Letters Only)

When you know the input contains only lowercase letters a-z, an array-based approach is faster:

JavaPython

Loading...

Which Implementation to Choose?

Aspect	Map/Dict	Array[26]
Character set	Any Unicode	Only a-z
Memory	Sparse, on-demand	26 pointers per node
Lookup speed	O(1) hash	O(1) direct index
LeetCode	More flexible	Slightly faster

Tip: For interviews, the array-based approach is often preferred for its simplicity when dealing with lowercase letters only.

---

Worked Example

Let’s trace through inserting “apple”, “app”, and “apply”:

Step 1: Insert “apple”

Start: Empty Trie with root

Insert 'a': root → a (new)
Insert 'p': a → p (new)
Insert 'p': p → p (new)
Insert 'l': p → l (new)
Insert 'e': l → e (new, mark as END)

Result:
    (root)
       |
       a
       |
       p
       |
       p
       |
       l
       |
       e ●   ← isEnd = true

Step 2: Insert “app”

Traverse 'a': exists, move to a
Traverse 'p': exists, move to p
Traverse 'p': exists, move to p → Mark as END

Result:
    (root)
       |
       a
       |
       p
       |
       p ●   ← isEnd = true (app)
       |
       l
       |
       e ●   ← isEnd = true (apple)

Step 3: Insert “apply”

Traverse 'a': exists
Traverse 'p': exists
Traverse 'p': exists
Insert 'l': exists, move to l
Insert 'y': l → y (new, mark as END)

Result:
    (root)
       |
       a
       |
       p
       |
       p ●
      /|
     l y ●   ← isEnd = true (apply)
     |
     e ●

---

Time & Space Complexity

Operation	Time	Space
Insert	O(m)	O(m) worst
Search	O(m)	O(1)
StartsWith	O(m)	O(1)

Where m = length of word/prefix.

Space Analysis

For n words of average length m:

• Worst case: O(n × m) - no shared prefixes
• Best case: O(m) - all words share common prefix
• Typical: Somewhere in between, depends on data

---

LeetCode 208: Implement Trie (LC 208)

This is the classic Trie implementation problem. The template above solves it directly.

// Usage example
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // true
trie.search("app");     // false (not marked as end)
trie.startsWith("app"); // true (prefix exists)
trie.insert("app");
trie.search("app");     // true (now marked as end)

---

LeetCode 211: Word Dictionary with Wildcards (LC 211)

Problem

Design a data structure that supports:

• addWord(word) - Adds a word
• search(word) - Returns true if word exists (. can match any letter)

Key Insight

When we encounter ., we must try all 26 children recursively.

JavaPython

Loading...

Complexity

• addWord: O(m)
• search without wildcard: O(m)
• search with wildcards: O(26^k × m) where k = number of . characters

---

LeetCode 212: Word Search II (LC 212)

Problem

Given an m × n board of characters and a list of words, find all words that can be formed by sequentially adjacent cells.

Why Trie Shines Here

Naive approach: For each word, DFS from every cell → O(n × m × words × 4^L)

Trie approach: Build Trie from words, DFS once → O(m × n × 4^L)

The Trie lets us check if our current path could lead to any word, enabling early pruning.

JavaPython

Loading...

Key Optimizations

1. Store word at end node - Avoid path reconstruction
2. Remove found words - Prevent duplicates
3. Prune empty branches - Remove nodes with no remaining words

---

Common Mistakes

1. Forgetting to Mark End

// ❌ Wrong: Never marks end of word
public void insert(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
        int idx = c - 'a';
        if (node.children[idx] == null) {
            node.children[idx] = new Trie();
        }
        node = node.children[idx];
    }
    // Missing: node.isEnd = true;
}

2. Confusing search vs startsWith

// search("app") with Trie containing "apple"
// Returns FALSE - "app" is not a complete word

// startsWith("app") with Trie containing "apple"  
// Returns TRUE - "app" is a valid prefix

3. Wrong Return in searchNode

// ❌ Wrong: Returns true for prefix
public boolean search(String word) {
    return searchNode(word) != null; // Should also check isEnd!
}

// ✅ Correct
public boolean search(String word) {
    Trie node = searchNode(word);
    return node != null && node.isEnd;
}

---

Interview Tips

How to Explain Trie

“A Trie is a tree where each node represents a character. The path from root to any node forms a prefix. Nodes marked as ‘end’ represent complete words. This structure allows O(m) insert, search, and prefix operations where m is the word length.”

Follow-up Questions

Q: How to find all words with a given prefix?

Navigate to prefix end node, then DFS to collect all words.

Q: How to delete a word?

Navigate to end node, unmark isEnd. Optionally prune empty branches.

Q: Memory optimization?

Use compressed Trie (radix tree) where single-child chains become one node with a string.

---

When NOT to Use Trie

1. Single exact lookup - HashMap is simpler and faster
2. Small word set - Overhead not worth it
3. Non-string keys - Trie is designed for sequences
4. Memory constrained - Each node has 26+ pointers overhead

---

Related LeetCode Problems

Problem	Difficulty	Key Concept
LC 208 - Implement Trie	Medium	Basic implementation
LC 211 - Word Dictionary	Medium	Wildcard with DFS
LC 212 - Word Search II	Hard	Trie + Board DFS
LC 677 - Map Sum Pairs	Medium	Trie with values
LC 648 - Replace Words	Medium	Find shortest prefix
LC 1268 - Search Suggestions	Medium	Autocomplete

---

Summary

Trie is your go-to when:

• ✅ Prefix operations are needed
• ✅ Many strings share common prefixes
• ✅ Lexicographic ordering matters
• ✅ Building autocomplete/spell checker

Key Template Pattern:

// Navigate to node
Trie node = this;
for (char c : word.toCharArray()) {
    int idx = c - 'a';
    if (node.children[idx] == null) {
        // Create or return null based on operation
    }
    node = node.children[idx];
}
// Mark end (insert) or check end (search)

Remember:

• search() = node exists AND isEnd is true
• startsWith() = node exists (don’t check isEnd)
• Array[26] for lowercase only, Map for flexible characters