⏱️ Lectura: 14 min
When you type prog in VS Code’s command palette and the list instantly filters down to program, progress, and profile, there’s no hash table behind it: there’s a trie, a tree that indexes words letter by letter instead of summarizing the whole word into a number.
📑 En este artículo
A trie (from the word retrieval, though almost everyone pronounces it like “try”) is the structure behind your IDE’s autocomplete, your phone’s spell checker, and the IP routing tables that decide which way each packet leaves on the internet. This guide explains it from scratch, with working code in JavaScript and Python.
TL;DR
- You’ll understand how a trie indexes words letter by letter, without using hashing.
- You’ll implement a trie from scratch in JavaScript with insert, search, and prefix lookup.
- You’ll build a real autocompleter that returns prefix-based suggestions in Python.
- You’ll know when a trie beats a hash table and when it loses on memory.
- You’ll distinguish a trie from a radix tree (PATRICIA) and why node compression exists.
- You’ll identify the most common mistakes when implementing a trie in production.
- You’ll be able to explain why IP routing uses tries instead of hash tables.
What a Trie Is and Why It Matters
A trie is a tree where every path from the root to a node represents a prefix, and every node marked as the end of a word represents a full stored key. The formal Wikipedia definition describes it as an ordered search tree that uses keys as strings, where a node’s position in the tree defines which key it’s associated with. Unlike a binary search tree, a trie doesn’t compare the full key against each node: it advances one character at a time.
The core advantage is that the search doesn’t depend on how many words the dictionary has, only on the length of the word being searched. Looking up “casa” in a trie with ten words or with ten million words takes the same number of steps: four, one per letter. That property, O(L) complexity where L is the key length rather than O(N) over the total number of keys, is what makes a trie ideal for autocomplete, spell checkers, and systems where the prefix matters more than exact equality.
A hash table, on the other hand, handles the question “does this exact key exist” well, but doesn’t efficiently answer “which keys start with this prefix.” For that, you’d have to walk through every key in the hash and filter one by one. A trie answers that second question natively: you land on the prefix’s node and walk through everything hanging off it.
How a Trie Works Internally
Every trie node has two things: a collection of children, one for each possible character that can follow, and a boolean flag indicating whether the path to that node forms a complete word. The root represents the empty string. Inserting a word means walking character by character from the root, creating child nodes when they don’t exist, and marking the last node as the end of a word.
flowchart TD
root(("root")) --> c["c"]
c --> ca["a"]
c --> cu["u"]
ca --> car["r (car)"]
car --> care["e (care)"]
ca --> cat["t (cat)"]
cu --> cup["p (cup)"]The diagram above shows a trie with car, care, and cat, plus cup. Notice that car and care share the same path up to the r, and that’s where they split: care continues with an extra e, while car already ends there, at a node marked as the end of a word. That share-as-much-as-possible principle is the essence of a trie: the more words share a prefix, the less extra memory the tree needs for each new word.
flowchart TD
A["Start: insert word"] --> B["node = root"]
B --> C{"Are there letters left in the word?"}
C -- "yes" --> D["take next letter"]
D --> E{"Does the node have a child with that letter?"}
E -- "no" --> F["create child node"]
E -- "yes" --> G["move to child node"]
F --> G
G --> C
C -- "no" --> H["mark current node as end of word"]The insertion algorithm is always the same loop: for each character in the word, check whether the current node already has a child with that character. If it doesn’t, create it. If it does, move forward. When it reaches the end of the word, mark the current node as the end of a word. Searching for a complete word follows the exact same path, but instead of creating nodes, it fails if a character doesn’t have the corresponding child. A prefix search is identical, except it doesn’t require the final node to be marked as the end of a word.
Practical Examples: Progressive Code
The first example implements the bare minimum: inserting words and confirming whether a word exists. The second adds the part you actually use every day: prefix-based suggestions, like the autocomplete in a search bar.
class TrieNode {
constructor() {
this.children = new Map();
this.esFinDePalabra = false;
}
}
class Trie {
constructor() {
this.raiz = new TrieNode();
}
insertar(palabra) {
let nodo = this.raiz;
for (const letra of palabra) {
if (!nodo.children.has(letra)) {
nodo.children.set(letra, new TrieNode());
}
nodo = nodo.children.get(letra);
}
nodo.esFinDePalabra = true;
}
buscar(palabra) {
let nodo = this.raiz;
for (const letra of palabra) {
if (!nodo.children.has(letra)) return false;
nodo = nodo.children.get(letra);
}
return nodo.esFinDePalabra;
}
}
const diccionario = new Trie();
diccionario.insertar("casa");
diccionario.insertar("caso");
console.log(diccionario.buscar("casa")); // true
console.log(diccionario.buscar("cas")); // falseThis trie uses a Map instead of a fixed 26-slot array, so it doesn’t waste memory when working with accents, ñ, or unicode. buscar(“cas”) returns false because “cas” was never marked as the end of a word, even though the path c-a-s does exist in the tree: that’s the kind of mistake that trips up people new to tries.
class NodoTrie:
def __init__(self):
self.hijos = {}
self.fin_palabra = False
class Autocompletador:
def __init__(self):
self.raiz = NodoTrie()
def insertar(self, palabra):
nodo = self.raiz
for letra in palabra:
nodo = nodo.hijos.setdefault(letra, NodoTrie())
nodo.fin_palabra = True
def _recolectar(self, nodo, prefijo, resultados, limite):
if len(resultados) >= limite:
return
if nodo.fin_palabra:
resultados.append(prefijo)
for letra, hijo in nodo.hijos.items():
self._recolectar(hijo, prefijo + letra, resultados, limite)
def sugerir(self, prefijo, limite=5):
nodo = self.raiz
for letra in prefijo:
if letra not in nodo.hijos:
return []
nodo = nodo.hijos[letra]
resultados = []
self._recolectar(nodo, prefijo, resultados, limite)
return resultados
buscador = Autocompletador()
for palabra in ["python", "pytest", "pyplot", "java", "javascript"]:
buscador.insertar(palabra)
print(buscador.sugerir("py")) # ['python', 'pytest', 'pyplot']sugerir(prefijo) first walks to the prefix’s node, just like buscar, and from there runs a depth-first search (DFS) collecting every complete word hanging off that point. This is literally the algorithm running behind any search bar with real-time suggestions.
Getting Started: Implementing and Using a Trie Step by Step
You don’t need to install anything to try the examples above: node autocomplete.js or python autocomplete.py run directly. For a real use case, follow these steps:
- Define your alphabet: does your key use only lowercase a-z, or do you need to support accents, ñ, and full unicode? If it’s the latter, use a Map or dict for the children instead of a fixed 26-slot array.
- Insert the full dictionary at startup: insertion is O(L) per word, but repeating it on every request is wasted work.
- Expose two public methods: buscar(clave) for exact existence, and sugerir(prefijo, limite) for autocomplete. Always cap the number of results: a single-letter prefix can have thousands of words hanging off it.
- Use a mature library if one exists: in Python, pygtrie (maintained by Google) implements tries with support for keys made up of lists, not just strings. Install it with pip install pygtrie.
To confirm your trie really avoids the full traversal, measure how many nodes sugerir() visits: it should equal the prefix length plus the size of the resulting subtree, never the total size of the dictionary. A simple counter inside _recolectar is enough to verify it.
Real-World Use Cases
Autocomplete and spell checking: any search bar that suggests as you type, whether it’s an IDE, a command finder, or a phone keyboard, walks a trie or a compressed variant of one. The Apache Lucene search engine, the foundation of Elasticsearch and Solr, uses finite state automatons (FST) that are, in essence, compressed, alphabetically sorted tries.
IP routing: a router’s routing tables don’t look for an exact IP, they look for the longest matching network prefix (longest prefix match). Each bit of the IP address acts as a character in a binary alphabet, and the router walks a binary trie to decide which network interface the packet goes out through.
Word game dictionaries and spell checkers: Scrabble solvers, spell checkers, and old T9 keyboard systems use tries to validate whether a sequence of letters can still form a valid word, without scanning the entire dictionary on every keystroke.
💡 Tip: if your typical prefix has few characters but the dictionary is huge, a trie clearly wins. If your keys are mostly random and you only need exact-match lookups, a simple hash table is usually faster and easier to maintain.
Common Mistakes and Best Practices
- Forgetting the end-of-word flag: if you insert “casa” and search for “cas”, a poorly implemented trie can return true just because the path exists. Always distinguish “the path exists” from “this is a complete word.”
- Using a fixed 26-slot array with Spanish text: that excludes accents and ñ outright, or forces you to normalize the text before inserting, which can be valid, but has to be an explicit decision, not an accidental bug.
- Not limiting sugerir() results: a short prefix in a large dictionary can have tens of thousands of words hanging off it. Without a cap, or without sorting by usage frequency, the full traversal gets expensive even though the algorithm itself is efficient.
- Using a trie for random keys with no shared prefixes: there, a trie wastes memory, one node per digit with nothing to share, and a simple hash table wins on every front.
- Not compressing single-child chains: a naive trie creates one node per character even when there’s no branching at all. For large dictionaries with little overlap, that’s wasted memory; the solution is a radix tree.
Comparison with Alternatives
| Structure | When to Use It | Advantage | Limitation |
|---|---|---|---|
| Trie | Autocomplete, prefixes, dictionaries | Native prefix search in O(L) | One node per character: high memory usage with many unique words |
| Hash table | Exact match, unrelated keys | O(1) average search and write | Doesn’t handle prefix searches without scanning everything |
| Balanced binary search tree | Sorted ranges, in-order iteration | Native in-order traversal in O(log N) | Compares the full key at every node: slower than a trie for prefixes |
| Radix tree (PATRICIA trie) | IP routing tables, very large dictionaries | Compresses non-branching chains: fewer nodes than a flat trie | More complex implementation than a naive trie |
Going Deeper
The practical problem with a naive trie is that if you have many long words with little overlap, you end up with a long chain of single-child nodes, spending an entire node per letter with no real branching. A radix tree or PATRICIA trie solves this by collapsing those chains into a single node that stores the full substring, not just one character.
flowchart LR
subgraph "Flat trie"
A1["c"] --> A2["a"]
A2 --> A3["r"]
A3 --> A4["r"]
A4 --> A5["o"]
end
subgraph "Compressed radix tree"
B1["carro"]
endThat compression is why real IP routing tables don’t use a naive bit-by-bit binary trie: they use PATRICIA-style variants, where a single node can represent an entire block of bits with no branching, drastically reducing the number of nodes to traverse and the memory used.
Another variant is the suffix trie, or its compressed version, the suffix tree, which indexes every suffix of a text instead of whole words. That makes it possible to answer whether a substring appears in the text in time proportional to the length of the substring being searched, no matter how long the original text is: it’s the foundation of genomic search tools and some source code search engines.
📌 Note: a trie with a Map per node in JavaScript has a real memory cost: every empty Map consumes its own memory. For dictionaries with millions of words in production, measure actual memory usage with your JavaScript or Python engine before assuming a trie saves memory just because it shares prefixes; sometimes a radix tree is more compact.
📖 Summary on Telegram: View summary
Your next step: add a method to the Autocompletador class that sorts sugerir(prefijo) by usage frequency instead of alphabetical order, by storing a counter on each end-of-word node.
Frequently Asked Questions
What does the word “trie” mean?
It comes from “retrieval.” Edward Fredkin proposed the term in 1960 to distinguish it from “tree,” although in practice almost everyone pronounces it the same as “try.”
What is the search complexity of a trie?
O(L), where L is the length of the key being searched. It doesn’t depend on how many total keys the trie has, unlike a balanced binary search tree, which is O(log N).
Does a trie use more memory than a hash table?
It depends on how much the keys overlap. If they share many prefixes, like words from the same language, a trie can be more compact. If the keys are mostly random with no common prefixes, a trie wastes memory on nodes that are barely reused.
What’s the difference between a trie and a binary search tree?
A binary search tree compares the full key at every node to decide whether to go left or right. A trie doesn’t compare keys: it uses each character to decide which child to descend into, and it can have more than two children per node.
Where are tries used in the real world?
Autocomplete in search bars and command palettes, spell checkers, IP routing tables as radix trees, text search engines using FSTs derived from tries, and word game dictionaries.
How do I optimize memory for a very large trie?
Use a radix tree (PATRICIA trie) to compress non-branching chains into a single node, or switch each node’s children from a fixed array to a Map or dict if your alphabet is large but sparse.
References
- Wikipedia: Trie: formal definition, history of the term, and complexity properties.
- Wikipedia: Radix tree: the compressed variant (PATRICIA) used in IP routing tables.
- Apache Lucene: a search engine that uses finite state automatons derived from tries to index text.
- Wikipedia: Autocomplete: context on suggestion systems built on structures like the trie.
📱 Enjoying this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day.
Imagen destacada: Foto de Rahul Mishra en Unsplash
0 Comments