Tries

A tree keyed by characters or bits that shares prefixes. Prefix search and longest-prefix match in time proportional to the key length.

Level: intermediate

What is it?

A trie (prefix tree) stores strings by character. Each node represents a prefix, edges are labeled with the next character, and a flag marks nodes where a whole word ends. Lookup, insert, and prefix queries cost O(L), where L is the length of the key, independent of how many keys are stored.

Why does it matter?

Autocomplete, spell-checking, and dictionary lookups need prefix queries that hash tables cannot do. IP routers use a binary trie (or a compressed form) to find the longest matching prefix for a destination address.

Mental model

A phone menu tree: press 1 for sales, then 2 for billing. Each key you type follows an edge, and every prefix you have typed so far is a node. Words that share a beginning share their path.

How it works

Each node holds a map from character to child and an end-of-word flag.
Insert and search walk one edge per character: O(L).
Prefix search: walk the prefix, then collect all words below that node.
Memory can be large: many nodes with sparse children. Compressed tries (radix trees) merge single-child chains.
Bitwise tries key on bits of an IP address to implement longest-prefix match in routing tables.
Alternatives for exact match are hash tables; for ordered keys, balanced trees.

Steps

Start at the root
Follow the edge for the next character
Create it if missing
Mark the last node as a word end
A prefix query stops at that node

Code example: Insert words, ask about prefixes

class Trie:
    def __init__(self):
        self.children, self.end = {}, False

    def insert(self, word):
        node = self
        for ch in word:
            node = node.children.setdefault(ch, Trie())
        node.end = True

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

t = Trie()
for w in ["car", "card", "care"]:
    t.insert(w)
print(t.starts_with("car"), t.starts_with("cat"))   # True False

Complexity and trade-offs

Time: Insert, search, and prefix check O(L) for key length L

Space: O(total characters) in the worst case; less with shared prefixes

Trade-offs

Fast prefix operations that hash tables cannot do
Higher memory use than a hash set; compression helps

Real-world usage

Autocomplete and spell-check suggestions
IP routing: longest-prefix match in forwarding tables
Dictionary and word-game solvers

Common mistakes

Using a trie for plain exact lookups where a hash table is smaller and simpler.
Forgetting the end-of-word flag, so 'car' looks present when only 'card' was inserted.
Allocating a 26-element array per node for a huge alphabet.

Interview questions

How does a trie support autocomplete?

Walk the typed prefix to its node, then traverse the subtree below it, collecting words (optionally ranked by frequency). The cost depends on the prefix length plus the size of the results, not on the dictionary size.

Trie versus hash set for storing words?

A hash set gives O(1) average exact membership with less memory. A trie supports prefix queries and ordered traversal in O(L), which a hash set cannot do efficiently.

How are tries used in IP routing?

A binary trie is indexed by the bits of a destination address. Following the bits and remembering the deepest node that holds a route gives the longest matching prefix, which is the rule routers use.