Tries

The search structures covered so far compared keys as whole units: whether two strings are equal, or which one is larger. When keys are strings, each of these comparisons means, in the worst case, examining as many characters as the string’s length.

A different approach is to treat the key not as a whole but as a sequence of characters. In that case, the key becomes not a node in the tree but a path; comparison proceeds not all at once but character by character.

A Key Is a Path

In a trie, each edge corresponds to a character. The characters along the path from the root to a node form the prefix that node represents.

        (root)
       /      \
     r          w
     |          |
     a          a
     |         / \
     t        v   i
     |        |   |
     e*       e*  t*     (* : a key ends here)
     |
     s*

This tree stores four keys: rate, rates, wave, wait. The rate and rates keys share a common prefix that is stored once; the only thing distinguishing them is that the e node is also marked as an end of key.

An end-of-key marker is required: traversing a path does not mean that path is a key. The path ra exists, but ra is not a key. Without this marker, the structure could only say which prefixes exist, not which strings are actually stored.

Cost: Dependent on Length, Not Count

Searching a trie means following the key’s characters in order. The number of steps equals the key’s length — independent of how many keys the tree holds.

$$O(m), \quad m = \text{key length}$$

This is an interesting contrast with the $O(\log n)$ of a balanced search tree: even with a million keys, searching for a ten-character key takes ten steps.

The comparison with a hash table is subtler. Search in a hash table is considered “constant,” but computing the hash value reads the entire key — that is, $O(m)$. The two structures have the same order of point-lookup cost; where they diverge is in operations the hash table cannot offer.

class Trie:
    """Stores character sequences by sharing prefixes."""

    def __init__(self) -> None:
        self.children: dict[str, "Trie"] = {}
        self.is_end_of_key = False

    def insert(self, word: str) -> None:
        node = self
        for char in word:
            node = node.children.setdefault(char, Trie())
        node.is_end_of_key = True

    def _find_node(self, prefix: str) -> "Trie | None":
        node = self
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def contains(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end_of_key

    def has_prefix(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def words_with_prefix(self, prefix: str) -> list[str]:
        """Returns all keys starting with the given prefix, sorted."""
        start = self._find_node(prefix)
        if start is None:
            return []
        result: list[str] = []

        def walk(node: "Trie", accumulated: str) -> None:
            if node.is_end_of_key:
                result.append(prefix + accumulated)
            for char in sorted(node.children):        # sorted traversal
                walk(node.children[char], accumulated + char)

        walk(start, "")
        return result


trie = Trie()
for word in ("cat", "cats", "car", "dog", "door"):
    trie.insert(word)

print(trie.contains("cats"), trie.contains("ca"))   # True False
print(trie.has_prefix("ca"))                        # True
print(trie.words_with_prefix("ca"))     # ['car', 'cat', 'cats']
print(trie.words_with_prefix("do"))     # ['dog', 'door']
print(trie.words_with_prefix("xy"))     # []

The fact that contains("ca") returns false demonstrates the function of the end-of-key marker: the path exists, but the key does not.

Prefix Queries

The trie’s distinguishing capability lies in the last two calls. Finding all keys that start with a prefix requires scanning every key in a hash table; in a trie, it suffices to descend to the prefix node and traverse its subtree.

Typical uses:

• Autocomplete. Candidates starting with the prefix the user has typed.
• Dictionaries and spell checking. Tracking existing prefixes, possible completions; spelling suggestions are produced by a traversal that allows small deviations in the tree.
• Routing tables. Longest-prefix matching in the Computer Networks curriculum is done with a trie that operates on address bits.
• Sorted traversal. Traversing the subtree in order yields keys in lexicographic order — an operation a hash table cannot offer.

The Memory Trade-off

The cost of a trie is memory. A node is created for every character, and every node carries a child mapping. For a set with a large alphabet and keys that do not share common prefixes, the tree can end up larger than its own data.

Two common compressions exist:

Path compression. Chains of single-child nodes are collapsed into a single node, and an edge carries a character sequence instead of a single character. This structure is called a compressed trie (radix tree); it yields a large gain when there are few keys and the keys are long.

Choice of child representation. For small alphabets, a fixed-size array (one slot per character) is fast but wastes space in sparse nodes; using a map reduces space at some cost to access speed.

Bit-Level Tries

Keys need not be strings. The bit sequence of any value can also serve as a path; in that case each node has at most two children, and the structure becomes a binary tree.

Its best-known application is network routing. An address prefix is the first $k$ bits of the address; longest-prefix matching means descending from the root and finding the deepest matching node. Routing table lookup in the Computer Networks curriculum is done with this structure.

The second application is dictionaries with integer keys. Compressed tries operating at the bit level are used as an alternative to hash tables: they offer sorted traversal and prefix queries, require no hash computation, and their worst-case guarantee is bounded by key width.

The bit-level operations from the How Computers Work course are used directly here as well: at each step, the relevant bit is read through shifting and masking.

Comparison

Metric	Trie	Hash table	Balanced search tree
Point lookup	$O(m)$	$O(m)$ average	$O(m \log n)$
Prefix query	Direct	Not supported	Partially, via range query
Sorted traversal	Yes	No	Yes
Memory	High	Moderate	Moderate
Worst case	$O(m)$	$O(n \cdot m)$	$O(m \log n)$

The values in the table assume keys are strings; for numeric keys, comparison has constant cost, and comparison-based structures take the lead.

The $\log n$ factor in a balanced search tree comes from performing a string comparison at every node — a trie has no such factor.

Summary

• In a trie, a key is stored not in a node but in a path descending from the root; common prefixes are kept once.
• An end-of-key marker is required; a path existing does not mean that path is a key.
• Search cost depends on key length and is independent of the number of stored keys.
• Listing all keys starting with a prefix means traversing the prefix node’s subtree.
• The cost is memory; path compression and the choice of child representation reduce that cost.
• Prefix queries and sorted traversal, which a hash table cannot offer, are this structure’s reason for existing.

Next Step

The structures covered so far operated on individual keys. In some problems, however, the query concerns a range: “what is the sum of the values between these two indices” — and this query is asked repeatedly while the data keeps changing. The next lesson covers structures that answer this question at logarithmic cost.