13. Tries

What Is a Trie?

A Trie (pronounced "try", from retrieval) is a tree structure where each path from root to a node spells out a string. Every character of a word is stored as a separate node.

Analogy: A dictionary organised by letter-by-letter branching. To look up "cat", go to the 'c' branch, then 'a', then 't'.

Real-world uses:

• Autocomplete — type "se" and get "search", "settings", "send"
• Spell checkers — verify word exists or find closest match
• IP routing tables — match longest prefix of an IP address
• Search engines — suggest queries as you type

---

13.1 Trie Implementation

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end_of_word: bool = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """Add a word to the trie — O(L) where L = word length."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        """Return True if the exact word exists — O(L)."""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        """Return True if any word starts with this prefix — O(L)."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

    def autocomplete(self, prefix: str) -> list[str]:
        """Return all words that start with prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        results = []
        self._dfs(node, prefix, results)
        return results

    def _dfs(self, node: TrieNode, current: str, results: list[str]) -> None:
        if node.is_end_of_word:
            results.append(current)
        for char, child in node.children.items():
            self._dfs(child, current + char, results)


# Usage
trie = Trie()
for word in ["apple", "app", "application", "apply", "banana", "band"]:
    trie.insert(word)

print(trie.search("app"))          # True
print(trie.search("ap"))           # False (not a full word)
print(trie.starts_with("ap"))      # True
print(trie.autocomplete("app"))    # ['app', 'apple', 'application', 'apply']
print(trie.autocomplete("ban"))    # ['banana', 'band']

---

13.2 When to Use a Trie vs a Hash Set

Scenario	Best Tool
Check if exact word exists	set — simpler, $O(1)$
Check if prefix exists	Trie — set can't do this efficiently
Autocomplete suggestions	Trie
Count words with prefix	Trie (store counts at nodes)
All words matching wildcard pattern	Trie with DFS

---