If you have ever needed to check thousands of prefixes, autocomplete a word, or find the pair of numbers with the largest XOR, the trie is the data structure that turns a slow brute-force solution into a clean, fast one.
A trie (also called a prefix tree) is a rooted tree that stores a set of strings by sharing their common prefixes. The root represents the empty string, every edge is labeled with a single character, and any path from the root spells out a prefix. Two words that begin the same way share the same path until they diverge. This simple idea is one of the most reliable tools in the trie competitive programming toolkit, and it shows up across string, dictionary, and bitwise problems.
Why Tries Are Fast
The defining advantage of a trie is that the cost of an operation depends on the length of the word, not on how many words you have stored. Insertion, search, and prefix queries all run in O(L) time, where L is the length of the string or prefix involved. Whether your dictionary holds ten words or ten million, looking up a 6-character key still takes about six steps.
Compared with a hash set, a trie offers something hash tables cannot: prefix awareness. Asking "how many stored words start with str?" or "is any stored word a prefix of this one?" is natural in a trie and awkward with hashing. The trade-off is memory. Because each node may branch into many children, tries can consume significant space, so contestants often store children in fixed-size arrays for small alphabets (like the 26 lowercase letters) and switch to maps for larger ones.
Quick intuition: a trie is just a deterministic finite automaton where each character advances you one node deeper. Marking the nodes where a complete word ends lets you distinguish a stored word from a mere prefix.
The Patterns That Win Contests
Most trie problems are variations on a handful of templates. Recognizing the pattern is usually harder than coding it. Students in our competitive programming program drill these until the structure becomes second nature:
- Dictionary and prefix counting: store a node counter so you can answer "how many words share this prefix" in O(L). This powers autocomplete-style problems.
- Word-break and matching: walk the text while descending the trie to detect when any stored pattern appears.
- Bitwise (binary) tries: store integers by their fixed-width binary representation, using only the digits 0 and 1.
- Multi-pattern search: the Aho-Corasick automaton, built directly on top of a trie.
Maximum XOR With a Binary Trie
One of the most elegant uses is the classic "find the maximum XOR of two numbers in an array" problem. Insert each integer into a binary trie from its most significant bit (MSB) to its least significant bit. To maximize the XOR for a query value, walk from the MSB down and, at each step, greedily try to follow the opposite bit; if that branch exists you gain a 1 in that position, otherwise you take the only branch available. Because XOR is decided bit by bit from the top, this greedy descent is provably optimal and runs in time proportional to the number of bits, often around 30 or 32. The same trick extends to constrained queries, where you insert numbers incrementally so each query only sees the values it is allowed to use.
Aho-Corasick: Tries for Many Patterns at Once
When you must search a long text for many patterns simultaneously, the Aho-Corasick algorithm shines. It builds a trie of all the keywords, then adds suffix links that jump to the longest proper suffix that is also a node in the trie, turning the trie into an automaton. This lets you scan the text once and report all matches in O(n + m + z) time, where n is the text length, m is the total pattern length, and z is the number of matches. This exact technique solves real contest tasks, including the USACO Gold problem "Censoring."
Master the plain trie first. Aho-Corasick, persistent tries, and bitwise tries all assume you can build and traverse a basic prefix tree without thinking.
How to Practice Effectively
Tries reward deliberate practice. Start by implementing one from scratch, then solve a graded ladder of problems: a dictionary lookup, a prefix-count task, a maximum-XOR question, and finally a multi-pattern matching challenge. Many of these appear on USACO and other contests in our competition catalog, so contest-driven practice keeps your skills sharp and measurable.
Ready to go from understanding tries to placing in real olympiads? Explore BIAA's competitive programming program to get structured problem ladders, code review, and coaching built around exactly these patterns.