trie
A trie is a tree built for storing strings, where the path you walk spells out the key rather than the key sitting in a single node. Each edge is labelled with one character, so the word 'cat' is the path c → a → t from the root. Words that share a prefix share the path that spells it: 'car' and 'cat' travel together through c → a before branching. The name comes from reTRIEval, and it is usually said like 'try' to tell it apart from 'tree'.
Looking up a key means following one character at a time from the root, so a search takes O(L) where L is the length of the string — and remarkably, it does not slow down as you store more words. That is a real advantage over a balanced search tree, whose O(log n) grows with the number of keys. A node is usually marked to say 'a complete word ends here', so 'car' and 'card' can both live in the structure at once.
Because the shared prefixes live in shared paths, a trie answers prefix questions almost for free: walk to the node for 'ca' and everything beneath it is a word starting with 'ca' — exactly what autocomplete, spell-checkers, and IP routing tables need. The price is memory: a naive node keeps a slot for every possible next character (say 26 for lowercase letters), so a sparse trie can waste a lot of space, which is why compressed variants like radix trees exist.
// root
// |c
// (c)
// |a
// (a)
// r/ \t
// (r)* (t)* <- car, cat
// |d
// (d)* <- card
struct TrieNode {
std::array<TrieNode*, 26> next{}; // a..z
bool isWord = false;
};Each child slot keyed by the next character; isWord flags a complete key.
Pronounced like "try" (from reTRIEval) to distinguish it from "tree"; lookup cost O(L) depends on key length, not on how many keys are stored.