Tries Explained: The Data Structure That Makes String Search Instant

A trie (pronounced "try," short for retrieval) is a tree where each path from root to node represents a prefix of some string in your dataset. It was invented for dictionary lookups but shows up in interview problems, autocomplete systems, IP routing tables, and spell checkers.

The insight that makes tries powerful: after inserting n words, searching for any word or prefix takes O(m) where m is the query length — completely independent of n.

---

Building the Trie

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False  # marks end of a complete word

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word: str) -> bool:
        """Returns True only if the exact word exists."""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end  # must be marked as complete word
    
    def starts_with(self, prefix: str) -> bool:
        """Returns True if any word starts with prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True  # prefix exists (don't care about is_end)

Visualise inserting "cat", "car", "card", "care":

root
 └── c
      └── a
           ├── t (is_end=True)  ← "cat"
           └── r (is_end=True)  ← "car"
                ├── d (is_end=True)  ← "card"
                └── e (is_end=True)  ← "care"

Key observations:

• "cat" and "car" share the prefix "ca" — stored once, not twice
• is_end=True at "r" lets us find "car" even though "card" and "care" extend beyond it
• starts_with("car") → True (node exists); search("ca") → False (is_end=False at "a")

---

Time and Space Complexity

| Operation | Time | Space | |---|---|---| | Insert word of length m | O(m) | O(m) per new word | | Search word of length m | O(m) | O(1) | | Prefix search of length m | O(m) | O(1) | | Total space for n words, avg length m | — | O(n × m) worst case |

Vs hash map: A hash map search("cat") is O(m) for hashing but can't answer "does any word start with 'ca'?" without scanning all keys. A trie handles prefix queries natively.

---

Extended Operations

Count words with prefix

def count_words_with_prefix(self, prefix: str) -> int:
    node = self.root
    for char in prefix:
        if char not in node.children:
            return 0
        node = node.children[char]
    return self._count_words(node)

def _count_words(self, node: TrieNode) -> int:
    count = 1 if node.is_end else 0
    for child in node.children.values():
        count += self._count_words(child)
    return count

Delete a word

def delete(self, word: str) -> bool:
    def _delete(node, word, depth):
        if depth == len(word):
            if not node.is_end:
                return False  # word doesn't exist
            node.is_end = False
            return len(node.children) == 0  # can delete if no children
        
        char = word[depth]
        if char not in node.children:
            return False
        
        should_delete_child = _delete(node.children[char], word, depth + 1)
        
        if should_delete_child:
            del node.children[char]
            return not node.is_end and len(node.children) == 0
        
        return False
    
    return _delete(self.root, word, 0)

Autocomplete — find all words with prefix

def autocomplete(self, prefix: str) -> list:
    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, current, results):
    if node.is_end:
        results.append(current)
    for char, child in node.children.items():
        self._dfs(child, current + char, results)

---

Interview Problem 1: Word Search II

Problem: Given a board of characters and a list of words, find all words that exist in the board (connect adjacent cells horizontally/vertically).

Naive approach: BFS/DFS from every cell for every word → O(words × cells × 4^max_length). TLE.

Trie approach: Insert all words into a trie. DFS from each cell, following trie paths. If the path dies in the trie, prune early. Collect complete words when is_end=True.

def find_words(board, words):
    trie = Trie()
    for word in words:
        trie.insert(word)
    
    rows, cols = len(board), len(board[0])
    result = set()
    
    def dfs(node, r, c, path):
        char = board[r][c]
        if char not in node.children:
            return   # prune: no word in trie continues with this char
        
        next_node = node.children[char]
        path += char
        
        if next_node.is_end:
            result.add(path)
            next_node.is_end = False  # avoid duplicates
        
        board[r][c] = '#'  # mark visited
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                dfs(next_node, nr, nc, path)
        board[r][c] = char  # restore
    
    for r in range(rows):
        for c in range(cols):
            dfs(trie.root, r, c, "")
    
    return list(result)

Why it's faster: The trie prunes entire branches. If "abc" isn't a prefix of any word, we stop after 3 characters instead of exploring all paths of length 15+.

---

Interview Problem 2: Search Suggestions System

Problem: Given a list of products and a search query typed character by character, return up to 3 suggestions after each character is typed.

def suggested_products(products, search_word):
    # Insert all products into trie with word storage
    trie = Trie()
    for p in sorted(products):  # sort for lexicographic order
        trie.insert(p)
    
    result = []
    prefix = ""
    
    for char in search_word:
        prefix += char
        # Get up to 3 autocomplete results
        suggestions = trie.autocomplete(prefix)[:3]
        result.append(suggestions)
    
    return result

---

Interview Problem 3: Maximum XOR of Two Numbers

Problem: Find the maximum XOR of any two numbers in an array.

Key insight: Build a binary trie of all numbers. For each number, greedily navigate the trie to find the number that differs in as many high bits as possible (maximising XOR).

class BinaryTrieNode:
    def __init__(self):
        self.children = [None, None]  # children[0] = bit 0, children[1] = bit 1

class MaxXORTrie:
    def __init__(self):
        self.root = BinaryTrieNode()
    
    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):  # MSB to LSB
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = BinaryTrieNode()
            node = node.children[bit]
    
    def max_xor_with(self, num):
        node = self.root
        xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            opposite = 1 - bit
            if node.children[opposite]:
                xor |= (1 << i)   # we can set this bit in XOR
                node = node.children[opposite]
            else:
                node = node.children[bit]
        return xor

def find_maximum_xor(nums):
    trie = MaxXORTrie()
    for num in nums:
        trie.insert(num)
    
    return max(trie.max_xor_with(num) for num in nums)

---

When to Reach for a Trie

A trie is the right tool when:

1. Prefix matching is required: "Find all words starting with 'auto'", autocomplete, predictive text
2. You need to check many string prefixes efficiently: Word Search II, boggle solvers
3. Bit manipulation + maximum/minimum: XOR problems where you want to greedily pick bits
4. IP routing tables: Longest prefix match for network routing

A hash map is better when:

• You only need exact lookups (no prefix queries)
• Memory is very constrained (trie uses more memory than a hash set for small datasets)
• Words have high character diversity (trie nodes waste space on empty children)

---

Space Optimisation: Compressed Trie

If memory matters, a compressed trie (Patricia trie) merges chains of single-child nodes into one edge with a string label. This reduces nodes from O(total characters) to O(n words). Python's pygtrie library implements this if you need it in production.

---

Practice Problems

| Problem | Trie Variant | Difficulty | |---|---|---| | Implement Trie (LeetCode #208) | Basic | Medium | | Add and Search Word (#211) | Wildcard . in search | Medium | | Word Search II (#212) | Trie + DFS on grid | Hard | | Search Suggestions System (#1268) | Trie + autocomplete | Medium | | Maximum XOR of Two Numbers (#421) | Binary trie | Medium | | Palindrome Pairs (#336) | Trie + reversed words | Hard |

Build it before using it: Before solving any trie problem, implement insert, search, and starts_with from memory. It takes 15 minutes and removes all the mechanical uncertainty. Then the actual problem is just using your tool. Practice the basics in SCS Practice under "Trees".