Trie

A Trie (pronounced "try", from retrieval) is a tree-like data structure for storing strings where each node represents a character.

The Phone Book Analogy: Imagine a phone book organized by first letter, then second letter, etc.:

• •Looking up "Smith" → S section → Sm section → Smi → Smit → Smith
• •Once you're in the "Sm" section, you've eliminated all names not starting with "Sm"

Visual Structure:

Key Properties:

• •Root is empty (represents empty prefix)
• •Each edge represents a character
• •Path from root = prefix
• •isEnd flag marks complete words
• •Shared prefixes share nodes (memory efficient for similar words)

Tries solve prefix problems that HashMap cannot efficiently handle.

The Killer Feature: Prefix Operations

What Interviewers Test:

1. •Data Structure Design - Can you implement from scratch?
2. •Prefix Understanding - Why Trie over HashMap?
3. •Combining Patterns - Trie + DFS/BFS/Backtracking
4. •Optimization Thinking - Array vs HashMap children

Frequency in Interviews:

• •Google, Facebook: Very common for autocomplete systems
• •LeetCode: ~15 Trie problems, several are hard
• •Most common: Implement Trie, Word Search II, Autocomplete

Real-World Uses:

• •Autocomplete/Typeahead
• •Spell checkers
• •IP routing (longest prefix match)
• •Phone directories
• •DNA sequence matching

Before implementing Trie, understand the node structure.

Two Common Implementations:

1. Array-based (fixed alphabet):

• •Pro: O(1) child access
• •Con: Wastes space if few chars used
• •Best for: lowercase English letters only

2. HashMap-based (flexible):

• •Pro: Memory efficient for sparse alphabets
• •Con: HashMap overhead
• •Best for: Unicode, mixed case, large alphabets

Visual Comparison:

Additional Node Data:

Inserting a word creates the path if it doesn't exist.

Algorithm:

1. •Start at root
2. •For each character:
   • If child doesn't exist, create it
   • Move to child
3. •Mark final node as word end

Visual Trace - Insert "cat" then "car":

Key Insight: Shared prefixes share nodes. "cat" and "car" share "ca".

The most important distinction in Trie operations.

search(word): Does this EXACT word exist? startsWith(prefix): Does ANY word start with this prefix?

Example with Trie containing: ["apple", "app", "application"]

Results:

The Only Difference: search checks isEnd, startsWith doesn't.

The full implementation combining all basic operations.

What We Need:

1. •TrieNode class with children and isEnd
2. •insert(word) - add word to trie
3. •search(word) - check if exact word exists
4. •startsWith(prefix) - check if any word has prefix

LeetCode 208 - Implement Trie (Prefix Tree)

This is the foundation for all Trie problems. Master this implementation!

Given a prefix, find all words that start with it. The killer app for Tries!

Algorithm:

1. •Navigate to the prefix node
2. •If prefix doesn't exist, return []
3. •DFS from prefix node, collecting all complete words

Visual Trace:

Optimization: Store word at isEnd node Instead of rebuilding string during DFS, store the complete word.

LeetCode 1268: Return top 3 suggestions as user types each character.

Problem:

Approach:

1. •Build Trie from products
2. •For each prefix of searchWord:
   • Navigate to prefix node
   • DFS to get up to 3 lexicographically smallest words

Key Insight: DFS in alphabetical order naturally gives lexicographic results.

Support '.' wildcard that matches any single character.

LeetCode 211:

Algorithm: When we hit '.', try ALL children recursively. If ANY path succeeds, return true.

Visual Trace for search("b.d"):

Find all dictionary words in a 2D character grid. The hardest Trie problem!

LeetCode 212:

Why Trie?

• •Without Trie: For each word, search entire grid → O(words × m×n × 4^L)
• •With Trie: One DFS, match multiple words → O(m×n × 4^L)

Algorithm:

1. •Build Trie from all words (store word at end node)
2. •DFS from each cell, following Trie
3. •When node.word exists, found a word!
4. •Set node.word = null to avoid duplicates

Key Optimization: Prune branches - if current path isn't in Trie, stop.

LeetCode 648: Replace words with their root/prefix if it exists.

Problem:

Algorithm:

1. •Build Trie from dictionary roots
2. •For each word in sentence:
   • Traverse Trie character by character
   • If hit isEnd, return that prefix (shortest root)
   • If path ends, return original word

Key Insight: Stop at FIRST isEnd (shortest prefix wins).

Making the right choice for your problem.

Time Complexity Comparison:

L = word length, N = total words

Space Comparison:

Use Trie When:

• •Prefix operations needed (autocomplete, startsWith)
• •Pattern matching with wildcards
• •Finding longest common prefix
• •Word games (Boggle, Scrabble)
• •IP routing tables

Use HashMap When:

• •Only exact match needed
• •Memory is constrained
• •Words have few common prefixes
• •Simple dictionary operations

Master these to avoid interview pitfalls.

1. Empty String

2. Single Character Words

3. Prefix is Also a Word

4. Case Sensitivity

5. Non-Alphabetic Characters

6. Duplicate Insertions

7. Search After No Insert

Advanced techniques for better performance.

1. Compressed Trie (Radix Tree) Merge single-child chains into one edge.

2. Ternary Search Tree Each node has 3 children: less, equal, greater. Better memory than 26-way Trie.

3. Word Storage at Nodes

4. Pruning in Word Search II

5. Prefix Count

Quick reference for choosing the right approach:

Decision Tree:

Time Complexity:

• •Insert: O(L) where L = word length
• •Search: O(L)
• •StartsWith: O(L)
• •Autocomplete: O(L + total characters in results)
• •Wildcard with k dots: O(26^k × L) worst case
• •Word Search II: O(M × N × 4^L) where M×N = grid, L = max word length

Space Complexity:

Array-based (26 children):

• •O(N × L × 26) worst case
• •Each node: 26 pointers + boolean ≈ 208 bytes

HashMap-based:

• •O(N × L × avg_branching) average case
• •More memory efficient for sparse trees

Comparison for 10,000 words:

Trade-off: Trie uses more memory but provides O(L) prefix operations that HashMap cannot match.

Copy-paste ready templates.

Template 1: Basic Trie

Template 2: Wildcard Search

Template 3: Word Search II