A hashmap can tell you instantly whether cat is in your dictionary. Now ask it for every word that starts with ca. Hashing scatters keys on purpose, so the only way to answer is to scan all 100,000 entries. Autocomplete needs that question answered on every keystroke.

A trie (pronounced "try") is the structure built for exactly that question. It's like a word search puzzle, where each path from the start spells out a different word, letter by letter. Also known as a prefix tree, a trie is a tree that stores strings by breaking them down into individual characters. Unlike regular trees that store complete values at each node, tries build words character by character along paths, which makes them a natural fit for autocomplete and spell checking.

Tries let us add words by creating paths of letters, and find words by walking those paths one letter at a time. Since words with the same beginning share the same path, tries make it quick to look up a word or check whether it exists. Notice what's missing from the table below: the number of stored words. Looking up cat takes three steps whether the trie holds ten words or a hundred thousand, because every cost depends on the word's length, not the dictionary's size.

The efficiency of a trie depends on the alphabet size (often written as Σ), which is how many different characters we might use. If you're only storing lowercase English words, the alphabet size is 26. This matters because each node has to be ready to handle any character that might come next.

A trie node is like a single letter in a word puzzle: each node represents one character. Instead of storing complete words, each node uses a hashmap to track which letters can come next. That means words starting with the same letters share the same path. For example, car and cat would share the nodes for c and a before splitting into different paths.

class TrieNode:
    def __init__(self):
        self.children = {}  # Character -> TrieNode
        self.is_word = False

Here's a puzzle that exposes the missing piece: a trie stores only done, and you search for do. The walk succeeds, d then o, but do was never inserted. Should the search say yes? It shouldn't, and the fix is a boolean flag on each node marking whether it ends a real word. In a trie containing both do and done, the node for o flags itself as the end of a word, while still having a child node for n. Tries make it easy to check if a string is a complete word or just part of a longer one.

Inserting into a trie is like creating a new path through a forest, where we add new routes only when we need them. Starting at the root node, we walk through each character of our word, either following existing paths or creating new ones. If we want to insert cow and the trie already has cook, how many new nodes do we need? Just one. We reuse the path for co and only create a new node for w. That sharing is what makes tries memory-efficient.

# Insert word into trie - O(m)
def insert(self, word: str) -> None:
    curr = self.root
    # Create path for each character
    for char in word:
        if char not in curr.children:
            curr.children[char] = TrieNode()
        curr = curr.children[char]
    # Mark the end of the word
    curr.is_word = True

Once the path for the word exists, we need to mark its end. Setting an end-of-word flag on the final node lets us tell complete words apart from prefixes. The isWord boolean is the same flag the done puzzle called for earlier, and lets us store multiple words that share the same beginning while still knowing exactly where each one ends.

Deleting from a trie takes more care than insertion because we have to preserve shared paths used by other words. The first step is simple. We follow the path of characters and unmark the end-of-word flag when we land on our target word. For example, if the trie has both to and top and we want to delete to, we just remove its word marker. The nodes themselves stay in place because top still needs them.

# Delete word from trie - O(m)
def delete(self, word: str) -> None:
    curr = self.root
    # Follow the path for each character
    for char in word:
        if char not in curr.children:
            return  # Word not in trie
        curr = curr.children[char]
    # Unmark the end of the word
    curr.is_word = False

The deletion process follows the word's path through the trie, the same walk a search does. If at any point we can't find the next character, or if we reach the end and it isn't marked as a word, there's nothing to delete and we return. When we do find the word, we set its end-of-word flag to False and leave the nodes in place for any other words that share the path.

Searching in a trie is like following a trail of breadcrumbs. We check each character one at a time, starting from the root, and follow child nodes that match. Unlike a real breadcrumb trail, the path forks at every node, and the next character of the query decides which fork to take. If we ever can't find a matching child, the word isn't in the trie. Even if we make it to the end of the word, we still have to check whether that final node is marked as a word. Otherwise we'd treat partial matches like "ca" as words just because they're prefixes of something we stored.

# Search for complete word in trie - O(m)
def search(self, word: str) -> bool:
    curr = self.root
    for char in word:
        if char not in curr.children:
            return False
        curr = curr.children[char]
    # Check if this node marks end of a word
    return curr.is_word

# Search for prefix in trie - O(m)
def starts_with(self, prefix: str) -> bool:
    curr = self.root
    for char in prefix:
        if char not in curr.children:
            return False
        curr = curr.children[char]
    # Don't need to check is_word for prefix
    return True

Searching for prefixes works almost the same way, with one difference: we don't need to check the word flag at the end. If we can follow the path of characters to reach a valid node, the prefix is in the trie. It doesn't matter whether that node marks the end of a word or not. This is exactly what makes tries great for autocomplete, where you need every word that starts with a given prefix.

Tries are the right tool for storing and searching words or sequences when prefixes matter. Autocomplete, spell-check, and word puzzles are classic examples. Here are a few tips for using tries well in coding interviews:

First, two checks from this page: why doesn't a trie lookup get slower as the dictionary grows? And what goes wrong if you forget the end-of-word flag? If both are easy, you're set. Tries make prefix problems collapse from O(n*m) to O(m). Most of the work is just implementing the structure cleanly, and the rest is recognizing when a prefix tree is the right tool. Work through these to internalize the patterns: