Tries

A trie (prefix tree) is a tree where each node represents a character and paths from root to nodes spell out prefixes. It gives O(k) lookup where k is the key length, regardless of how many keys are stored.

Why It Matters

Tries power autocomplete, spell checking, IP routing tables, and dictionary lookups. Any problem involving prefix matching or shared prefixes benefits from a trie.

How It Works

Insert: "cat", "car", "card", "dog"

        (root)
        /    \
       c      d
       |      |
       a      o
      / \     |
     t   r    g*
     *   |
         d*

* = marks end of a complete word

Operations

Operation	Time	Notes
Insert	O(k)	k = key length
Search	O(k)	Exact match
Prefix search	O(k)	Check if any word starts with prefix
Delete	O(k)	Remove word, clean up empty branches
Autocomplete	O(k + m)	k = prefix, m = matches to enumerate

Code Example

class TrieNode:
    __slots__ = ('children', 'is_end')
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word: str):
        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._find_node(word)
        return node is not None and node.is_end
 
    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None
 
    def autocomplete(self, prefix: str) -> list[str]:
        node = self._find_node(prefix)
        if not node:
            return []
        results = []
        self._collect(node, prefix, results)
        return results
 
    def _find_node(self, prefix: str):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node
 
    def _collect(self, node, prefix, results):
        if node.is_end:
            results.append(prefix)
        for ch, child in sorted(node.children.items()):
            self._collect(child, prefix + ch, results)
 
# Usage
t = Trie()
for word in ["cat", "car", "card", "care", "dog", "do"]:
    t.insert(word)
 
assert t.search("car") == True
assert t.search("ca") == False
assert t.starts_with("ca") == True
assert t.autocomplete("car") == ["car", "card", "care"]
assert t.autocomplete("do") == ["do", "dog"]

Trie vs Hash Table

	Trie	Hash Table
Exact lookup	O(k)	O(k) for hashing + O(1) amortized
Prefix queries	O(k)	Not supported (must scan all keys)
Ordered iteration	Yes (alphabetical)	No
Memory	High (pointer per char)	Lower
Best for	Prefix search, autocomplete	Exact key-value lookup

Optimizations

• Compressed trie (radix tree) — merge single-child chains into one node, reducing memory
• Ternary search tree — binary search at each level, less memory than a trie

Related

• Trees and Binary Search Trees — tries are a type of tree
• Hash Tables — alternative for exact key lookup
• Arrays — can represent trie children as fixed-size arrays for speed
• BFS and DFS — trie traversal uses DFS