🔤 Tries

The Autocomplete Analogy

When you type in a search box:

You type: "app"
Suggestions: apple, application, approve, append...

How does it find all words starting with "app" so fast?

A trie stores words in a tree where each path from root spells out a word. Searching for a prefix is just following that path - no scanning every word!

Trie Structure

Storing Words: app, apple, apply, apt

        (root)
           |
           a
           |
           p
          / \
         p   t*
        /|
       l* y*
       |
       e*
       |
       (end)

* = end of a word

How It Works

Path from root:
  a → p → p → l → e = "apple"
  a → p → p → l → y = "apply"
  a → p → p = "app"
  a → p → t = "apt"

Each node can have up to 26 children (for a-z).

Why Tries Are Fast

Comparing to Other Structures

Search for "apple" in 100,000 words:

Hash Table: O(k) where k = word length
  Hash "apple", check exact match

Array/List: O(n × k)
  Check each of 100,000 words

Trie: O(k) where k = word length
  Follow 5 edges: a → p → p → l → e

For prefix search "app*":

Hash Table: O(n) - must check all words!
Trie: O(k + m) - k to find prefix, m for matches

Tries excel at prefix operations - things hash tables can't do efficiently.

Trie Operations

Insert: O(k)

Insert "cat":

(root) → c (create) → a (create) → t* (create, mark end)

Follow existing path or create new nodes.

Search: O(k)

Find "cat":

(root) → c (exists?) → a (exists?) → t (exists? is end?)
         ✓            ✓             ✓ and marked as word end

Return true!

Prefix Search: O(k + m)

Find all words starting with "ca":

Navigate to c → a
Then collect all words in that subtree:
  cat, car, card, care, ...

Delete: O(k)

Unmark word end, optionally remove nodes if no longer needed.

Time Complexities

k = length of word, m = number of matches

Note: Independent of how many words are stored! Just depends on word length.

Where Tries Are Used

1. Autocomplete

User types: "prog"
Trie instantly finds: program, programming, progress, ...

Much faster than scanning all words!

2. Spell Checkers

Is "recieve" a word?
Navigate trie - path doesn't exist or doesn't end at word.
Suggest: "receive" (exists in trie)

3. IP Routing

Longest prefix matching for network routes:
192.168.*.* → Route A
192.168.1.* → Route B

Trie finds best matching prefix quickly.

4. Word Games (Scrabble, Boggle)

"Is 'QI' a valid word?"
"What words can I make with these letters?"

Tries enable fast validation and search.

5. Search Engines

Index terms by prefix for instant suggestions.
"pyth" → python, pythagoras, pythonic, ...

Classic Trie Problems

1. Word Search II (Boggle)

Board:        Words: ["oath", "eat"]
o a a n
e t a e
i h k r
a i f l

Use tries to efficiently check valid words while exploring board.

2. Implement Trie

insert("apple")
search("apple") → true
search("app") → false
startsWith("app") → true
insert("app")
search("app") → true

3. Replace Words

Dictionary: ["cat", "bat", "rat"]
Sentence: "the cattle was rattled by the battery"

Replace with shortest root:
"the cat was rat by the bat"

4. Longest Word with All Prefixes

Words: ["w", "wo", "wor", "worl", "world"]

"world" is valid because:
  "w" is a word ✓
  "wo" is a word ✓
  "wor" is a word ✓
  "worl" is a word ✓
  "world" is a word ✓

Trie vs Hash Table

Use trie when:

• Need prefix operations
• Want alphabetical ordering
• Building autocomplete/spell check

Use hash table when:

• Only exact match needed
• Memory is constrained

Space Optimization

The Problem

Each node could have 26 children for alphabet → lots of null pointers!

Solutions

1. Use Hash Map for Children

Instead of array[26], use map: {'a': node, 'p': node}
Only store children that exist.

2. Compressed Tries (Radix Trees)

Merge single-child chains:
  a → p → p → l → e
  becomes:
  "apple" → (end)

Common Mistakes

1. Forgetting to Mark Word End

Just reaching a node doesn't mean it's a word! Must explicitly mark.

2. Not Handling Empty String

Empty string is valid input - don't crash!

3. Case Sensitivity

"Apple" vs "apple" - decide and be consistent.

4. Memory with Large Alphabets

Unicode has thousands of characters. Use hash maps for children!

FAQ

Q: Trie vs hash table for dictionary?

Hash table for exact lookups only. Trie for prefix operations, autocomplete, suggestions.

Q: How much memory do tries use?

Potentially a lot - each node has overhead. Use compressed tries for production.

Q: Can tries store numbers?

Yes! Treat digits as characters. Useful for phone number lookup.

Q: What's a radix tree?

A compressed trie where chains of single-child nodes are merged into one edge.

Summary

A trie is a tree structure that stores strings by their prefixes, enabling fast prefix operations.

Key Takeaways:

• Each path from root spells a word
• All operations are O(k) where k = word length
• Excellent for: autocomplete, spell check, prefix search
• Not efficient for: exact-match-only scenarios (use hash table)
• Space can be high - use compression for production
• Common in search, text processing, networking

Tries power the autocomplete you use every day!