What is a trie, and why use one?.

What is a trie?

A trie is a tree-based structure for storing collections of strings. The word comes from reTRIEval — to find or get something back.

It can also store numbers as binary (or decimal) strings.

Strings sharing a prefix share ancestors in the trie. That makes tries efficient for storing many strings and searching them — including prefix search, which hash tables can’t do.

Why use a trie?

• Prefix search: impossible with a hash table, natural in a trie.
• No collisions: better worst-case complexity than a poorly implemented hash table.
• No hash functions involved at all.
• Search in $O(k)$, where $k$ is the query length — sometimes less, when the query is absent.

Structure of a trie

Like a tree: a root node branching into children over multiple edges. Each TrieNode holds an array of child pointers, one index per character. Each node represents a string; each edge a character; the root is the empty string.

Every level represents prefixes of a given length: root (level 0) is the empty prefix, level 1 is prefixes of length 1, and so on. Strings sit sorted lexicographically left to right — which becomes clear when implementing insert.

Real-world applications

1. Autocomplete — type a prefix, get suggestions sharing it. The shared ancestors make this efficient; rank suggestions below them by popularity.
2. Spell checkers — check dictionary membership; on miss, suggest nearby words, optionally popularity-sorted.
3. String matching — match a pattern against a collection of strings.

Disadvantage

Memory. Each node carries a child-pointer array plus extras (like the wordEndCnt in my TrieNode), so tries are heavier than alternatives per string stored.

Range query trie

My go-to advanced use: binary tries for xor range queries. Solved problems live in Qs/:

1. Maximum xor subarray.
2. Count subarrays with xor less than k — tutorial.
3. Minimum K with at least X subarrays of xor at most K.
4. Count pairs with xor in a range.

Idea credit: theabbie on Codeforces, plus this and this discussion. Related reading: wavelet trees (1, 2) and sparse segtrees (USACO guide).