Trie¶
A tree of letters. Each path from the root spells a prefix, and words that share a beginning share the same path. Looking up a word, or every word that starts with "mar", costs only the length of the word.
| Insert / look up a word of length \(m\) | Words with a prefix | Space |
|---|---|---|
| \(O(m)\) | \(O(m + \text{output})\) | up to one node per letter stored |
The name comes from retrieval (Fredkin, 1960); most people say "try".
The idea¶
Your phone suggests "march", "marble" and "mare" as soon as you type "mar". It keeps the dictionary as a trie: the root has a branch for each first letter; under "m" there is a branch for each second letter; and so on. A node is marked when a whole word ends there.
- Insert: walk down the letters, creating missing nodes; mark the last node.
- Look up: walk down; the word is present if the walk succeeds and ends on a marked node.
- Prefix search: walk down the prefix, then list everything below that node.
- Count by prefix: store in each node how many words pass through it.
The cost depends only on the length of the word, not on how many words are stored, and words never have to be compared with each other.
How it works¶
Each node keeps a map from letter to child, an end flag and a count. The code uses an ordered map (Python
sorts at listing time), so words come out in alphabetical order.
Code¶
class TrieNode:
def __init__(self):
self.children = {} # letter -> next node
self.end = False # does a word end here?
self.count = 0 # how many words pass through here
class Trie:
"""A prefix tree of words: insert, look up and count by prefix in O(length of the word)."""
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.count += 1
node.end = True
def _walk(self, s):
node = self.root
for ch in s:
node = node.children.get(ch)
if node is None:
return None
return node
def contains(self, word):
node = self._walk(word)
return node is not None and node.end
def count_prefix(self, prefix):
node = self._walk(prefix)
return 0 if node is None else node.count
def with_prefix(self, prefix):
"""All stored words that start with prefix, in alphabetical order."""
out = []
def dfs(node, path):
if node.end:
out.append(path)
for ch in sorted(node.children):
dfs(node.children[ch], path + ch)
node = self._walk(prefix)
if node is not None:
dfs(node, prefix)
return out
if __name__ == "__main__":
t = Trie()
for w in ["mars", "marble", "march", "mare", "moon", "moonlight", "map"]:
t.insert(w)
print(t.contains("mars"), t.contains("mar"), t.contains("moonlit"))
print(t.count_prefix("mar"), t.count_prefix("moon"), t.count_prefix("x"))
print(t.with_prefix("mar"))
print(t.with_prefix("mo"))
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class Trie {
static class Node {
final Map<Character, Node> children = new TreeMap<>(); // letter -> next node, kept in order
boolean end; // does a word end here?
int count; // how many words pass through here
}
final Node root = new Node();
/** A prefix tree of words: insert, look up and count by prefix in O(length of the word). */
void insert(String word) {
Node node = root;
for (char ch : word.toCharArray()) {
node = node.children.computeIfAbsent(ch, c -> new Node());
node.count++;
}
node.end = true;
}
Node walk(String s) {
Node node = root;
for (char ch : s.toCharArray()) {
node = node.children.get(ch);
if (node == null) return null;
}
return node;
}
boolean contains(String word) { Node n = walk(word); return n != null && n.end; }
int countPrefix(String prefix) { Node n = walk(prefix); return n == null ? 0 : n.count; }
/** All stored words that start with prefix, in alphabetical order. */
List<String> withPrefix(String prefix) {
List<String> out = new ArrayList<>();
Node n = walk(prefix);
if (n != null) dfs(n, new StringBuilder(prefix), out);
return out;
}
void dfs(Node node, StringBuilder path, List<String> out) {
if (node.end) out.add(path.toString());
for (Map.Entry<Character, Node> e : node.children.entrySet()) {
path.append(e.getKey());
dfs(e.getValue(), path, out);
path.deleteCharAt(path.length() - 1);
}
}
static String py(boolean b) { return b ? "True" : "False"; }
static String show(List<String> xs) {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < xs.size(); i++) sb.append(i > 0 ? ", " : "").append("'").append(xs.get(i)).append("'");
return sb.append("]").toString();
}
public static void main(String[] args) {
Trie t = new Trie();
for (String w : new String[]{"mars", "marble", "march", "mare", "moon", "moonlight", "map"}) t.insert(w);
System.out.println(py(t.contains("mars")) + " " + py(t.contains("mar")) + " " + py(t.contains("moonlit")));
System.out.println(t.countPrefix("mar") + " " + t.countPrefix("moon") + " " + t.countPrefix("x"));
System.out.println(show(t.withPrefix("mar")));
System.out.println(show(t.withPrefix("mo")));
}
}
#include <iostream>
#include <map>
#include <memory>
#include <string>
#include <vector>
using namespace std;
struct Node {
map<char, unique_ptr<Node>> children; // letter -> next node, kept in order
bool end = false; // does a word end here?
int count = 0; // how many words pass through here
};
// A prefix tree of words: insert, look up and count by prefix in O(length of the word).
struct Trie {
Node root;
void insert(const string& word) {
Node* node = &root;
for (char ch : word) {
auto& next = node->children[ch];
if (!next) next = make_unique<Node>();
node = next.get();
node->count++;
}
node->end = true;
}
const Node* walk(const string& s) const {
const Node* node = &root;
for (char ch : s) {
auto it = node->children.find(ch);
if (it == node->children.end()) return nullptr;
node = it->second.get();
}
return node;
}
bool contains(const string& w) const { const Node* n = walk(w); return n && n->end; }
int countPrefix(const string& p) const { const Node* n = walk(p); return n ? n->count : 0; }
// All stored words that start with prefix, in alphabetical order.
vector<string> withPrefix(const string& prefix) const {
vector<string> out;
string path = prefix;
if (const Node* n = walk(prefix)) dfs(n, path, out);
return out;
}
static void dfs(const Node* node, string& path, vector<string>& out) {
if (node->end) out.push_back(path);
for (auto& [ch, child] : node->children) {
path.push_back(ch);
dfs(child.get(), path, out);
path.pop_back();
}
}
};
const char* py(bool b) { return b ? "True" : "False"; }
void show(const vector<string>& xs) {
cout << "[";
for (size_t i = 0; i < xs.size(); i++) cout << (i ? ", " : "") << "'" << xs[i] << "'";
cout << "]\n";
}
int main() {
Trie t;
for (string w : {"mars", "marble", "march", "mare", "moon", "moonlight", "map"}) t.insert(w);
cout << py(t.contains("mars")) << " " << py(t.contains("mar")) << " " << py(t.contains("moonlit")) << "\n";
cout << t.countPrefix("mar") << " " << t.countPrefix("moon") << " " << t.countPrefix("x") << "\n";
show(t.withPrefix("mar"));
show(t.withPrefix("mo"));
}
Output: True False False ("mar" is only a prefix, "moonlit" is absent); 4 2 0 words start with "mar", "moon"
and "x"; then the words under "mar" and under "mo", in alphabetical order.
When to use it¶
- Autocomplete and spell checking.
- Prefix counting: how many usernames start with "jo".
- IP routing: longest-prefix match on address bits (a binary trie).
- Word games: Boggle and crossword solvers prune any path that is not a prefix of a word.
- Maximum XOR of two numbers: a binary trie of the numbers' bits answers it in \(O(n \cdot \text{bits})\).
- For plain exact look-ups a hash table is usually simpler and uses less memory.
Common mistakes¶
- Forgetting the end mark: then "mar" is reported as a word just because "mars" is stored.
- Memory: a node with a 26-slot array per letter wastes space on sparse data; a map per node (as here) or a compressed trie saves it.
- Deleting a word must also remove nodes that no other word uses, and fix the counts.
Going deeper¶
Each part below starts closed; open the ones you want.
Sample walkthrough: the trie of mars, marble, march, mare, moon, moonlight, map
(root)
└ m
├ a
│ ├ p• map
│ └ r count 4
│ ├ b─l─e• marble
│ ├ c─h• march
│ ├ e• mare
│ └ s• mars
└ o─o─n• moon (count 2 at "moon")
└ l─i─g─h─t• moonlight
• marks the end of a word. Looking up "moonlit" walks m, o, o, n, l, i, then finds no "t" child of "i":
absent, after 6 steps.
The math: time and space
Time. Insert and look up visit one node per letter: \(O(m)\) map operations, each \(O(1)\) with a hash map, \(O(\log \sigma)\) with an ordered map over an alphabet of \(\sigma\) letters, or \(O(1)\) with a \(\sigma\)-slot array. Listing the words under a prefix costs \(O(m + T)\), where \(T\) is the size of the subtree.
Space. At most one node per letter of all the words together, \(O\!\left(\sum_w |w|\right)\), and less when words share prefixes. With \(\sigma\)-slot arrays the space is \(O\!\left(\sigma \sum_w |w|\right)\).
Comparison with a balanced search tree of \(n\) strings: a look-up makes \(O(\log n)\) string comparisons, each up to \(O(m)\), so \(O(m \log n)\) in the worst case, against the trie's \(O(m)\).
Expected depth of a random trie of \(n\) random binary strings is about \(\log_2 n\), like a balanced tree, because random prefixes split the set roughly in half at each level.
Watch it step by step
Orange is the path of the word being inserted, blue its new nodes, green nodes where a word ends.
Variations and related ideas
- Radix tree / Patricia trie: chains of single-child nodes are merged into one edge with a string label. Used in routers and in the Linux kernel.
- Ternary search tree: each node has a letter and three children (less, equal, greater); less memory than arrays of children.
- Aho–Corasick: a trie of many patterns plus "failure links" (like KMP's) finds every pattern in a text in one pass.
- Suffix tree / suffix trie: a trie of all suffixes of a text answers "does this pattern occur?" in \(O(m)\); it can be built in \(O(n)\) (Ukkonen, 1995).
See also¶
- Hash table: exact look-ups
- KMP: pattern matching, which Aho–Corasick extends to a trie
References¶
- E. Fredkin, "Trie memory", Communications of the ACM 3(9), 1960.
- D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd ed., §6.3 (digital searching).
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., §5.2 (tries).