Trie
A trie (pronounced "try," from re-trie-val) is a tree-based data structure for storing strings where each node represents a single character. The root repr...
The Prefix Tree and Its Node Structure
A trie (pronounced "try," from re-trie-val) is a tree-based data structure for storing strings where each node represents a single character. The root represents an empty string. Each path from the root to a node spells out a prefix, and each path from the root to a marked end-node spells out a complete word stored in the trie. Tries are also called prefix trees because they naturally group strings by shared prefixes.
Each node typically contains an array (or hash map) of child pointers — one per possible character — and a boolean flag indicating whether the node marks the end of a valid word. For lowercase English letters, each node holds an array of 26 pointers. For arbitrary Unicode characters, a hash map is more practical.
The depth of a node equals the length of the prefix it represents. Inserting a word of length L, searching for a word, and checking whether a prefix exists all run in O(L) time, independent of the number of words stored in the trie. This is a significant advantage over hash sets for prefix-related operations, since a hash set cannot answer "how many words start with 'pre'?" efficiently.
Insert, Search, and Prefix Operations
To insert a word: start at the root, iterate through each character of the word, follow the corresponding child pointer (creating a new node if the child does not exist), and after the last character mark the node as an end-of-word node. Insertion runs in O(L) time and O(L) space for a word of length L, but if prefixes are shared with existing words, the actual new node count is less.
To search for a word: traverse the trie character by character following child pointers. If any pointer is null, the word is absent. If you reach the last character, return the end-of-word flag. To check if a prefix exists: same traversal but return true as soon as you finish the prefix, regardless of the end-of-word flag.
Space for a trie storing W words with average length L using 26-child arrays is O(26 times W times L) in the worst case (no shared prefixes), but in practice, common prefixes share nodes, reducing space significantly. Using a hash map of children reduces wasted space at the cost of a small constant factor in lookup time.
Worked Example and Competitive Use Cases
Worked example: insert "apple," "app," and "apt" into a trie. After inserting "apple": root → a → p → p → l → e (end). After inserting "app": nodes root, a, p, p already exist; mark the second p as end. After inserting "apt": nodes root, a, p already exist; create child t and mark it as end. Searching "app" returns true (the second p is marked). Searching "ap" returns false (p is not marked). Checking prefix "ap" returns true (node p exists after root-a-p).
Tries are used for autocomplete engines, spell checkers, IP routing tables (where each bit of an IP address is a trie branch), and solving word games. The Aho-Corasick algorithm, used for multi-pattern string matching in antivirus software, builds on a trie by adding failure links similar to the KMP failure function.
Interview tip: whenever a problem involves a large dictionary and repeated prefix queries, propose a trie. A common question is "given a list of words, find all words that start with a given prefix." A trie answers this in O(P plus K) time where P is the prefix length and K is the number of matching words — far faster than scanning all words in the dictionary. Also mention that a compressed trie (radix tree) merges single-child chains to reduce node count.