--- title: Tries source: 'https://academia.sh/en/courses/data-structures/tries' course: 'Data Structures' language: en updated: '2026-08-17T18:08:05+00:00' license: 'CC BY-SA 4.0' --- # Tries The key becoming a path, sharing common prefixes, prefix queries, and the memory–speed trade-off. 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. ```python 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.