Trie (Prefix Tree)

A Trie is a tree where each path from root to a node spells out a prefix of one or more stored strings. It enables $O(L)$ insert and lookup (where $L$ is the string length), which beats a hash map when you need prefix queries.

Structure

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

Each node has up to 26 children (one per letter) and a flag marking whether any word ends here.

Insert and Search

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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

All three operations run in $O(L)$ time.

Why Not a Hash Set?

A hash set can check exact membership in $O(L)$ , but cannot answer prefix queries like "how many words start with 'pre'?" without scanning all keys. A Trie answers prefix queries in $O(L)$ plus result count.

Trie + DFS

Many trie problems combine traversal with DFS: walk the trie while DFS-ing a grid or word list.

Example: Word Search II — build a trie from the word list, then DFS the board. At each cell, follow the trie path to prune branches that cannot form any word.

When Do I Use This?

Signal	Trie is useful
"Prefix matching"	Yes
"All words starting with..."	Yes
"Autocomplete"	Yes
Just checking if a word exists	Hash set is simpler

Practice Problems

Done	Question	Difficulty
	Implement Trie Methods	Medium
	Prefix Matching	Medium