Characters as Edges: Compressing Vocabularies
A Trie (pronounced "try" or "tree") is a specialized tree structure used to store strings. If you store words in a standard Set, searching a word requires matching the entire string. If you search for a prefix, you have to iterate through the entire vocabulary.
A Trie solves this by decomposing strings into characters. Each node represents a common prefix, and links represent characters.
Prefix Compression
Words sharing prefixes (like cat, car, and card) share the same parent nodes in the tree. This eliminates storing duplicate character strings.
O(L) Search Runtime
Finding a word of length L takes exactly O(L) operations. The search speed is completely independent of the size of the database!
Interactive Prefix Tree Visualization
Type a prefix to watch the path light up, or insert custom words to draw nodes dynamically!
How to Represent Children
Each node in a Trie must know who its children are. There are two primary representations used in interviews:
1. Fixed Array: Node[26]
• Uses a fixed-size array of pointers (size 26 for lowercase English letters).
• Pros: Fast lookup (char - 'a' index). No hashing overhead.
• Cons: Highly wasteful in memory if nodes have only 1 child.
2. Hash Map: Map<char, Node>
• Children pointers are stored inside a dynamic lookup map.
• Pros: Space-efficient. Easily handles unicode, special characters, and uppercase keys.
• Cons: Slight hashing latency compared to direct array access.
Standard Trie (Insert, Search, StartsWith)
Importance
This is the standard LeetCode class implementation. search() looks for matching keys with isWord = true. startsWith() only verifies the prefix exists.
When to Use
• Implementing autocomplete dictionary lookups.
• Storing and matching IP routing prefixes.
• T9 predictive texting engines.
Prefix Autocomplete suggestions
Importance
In search queries, users want lists of suggestions starting with the prefix they typed.
How it Works
1. Walk to the prefix node (e.g., node a for prefix ca).
2. Trigger a DFS from that node, collecting all path sequences where isWord = true.
Radix Trees & Bitwise Tries
Radix Trees (Patricia)
Compresses memory by merging all nodes with single children. For example, the path r → o → a → d is compressed into a single edge holding string "road".
Bitwise Trie
Stores binary strings of integers. Used in advanced binary queries, like finding the maximum XOR pair in an array in O(N) time by walking opposite bits.
Trie vs HashSet vs Sorted Array
A Trie is not automatically the best structure for storing strings — it's only worth its memory overhead when you need prefix operations, not just exact lookups.
| Structure | Exact Lookup | Prefix Search | Reach for it when... |
|---|---|---|---|
| HashSet | O(L) hash + compare | O(N) — no order, must scan everything | You only ever check "does this exact word exist?" |
| Sorted Array | O(L log N) binary search | O(L log N) — two binary searches bound the range | The word list is static or rarely updated. |
| Trie | O(L) | O(L) to reach the node, then DFS to enumerate | You need many prefix ops (autocomplete, IP routing) and the set changes often. |
Common Mistakes
Forgetting isWord
A node existing on the path doesn't mean a word ends there. If only "card" was inserted, the path for "car" exists — but search("car") must still return false unless that node's isWord is true.
Node[26] Memory Blow-Up
A fixed-size array of 26 child pointers per node is fast, but most nodes in a real trie have only 1-2 children — the rest sit empty. On deep, sparse tries this wastes a lot of memory; a hash map trades a little speed for much better space usage.
Lowercase-Only Assumptions
The classic char - 'a' array index only works for lowercase a-z. Real input has uppercase letters, digits, unicode, or punctuation — an array-indexed trie breaks silently (or crashes) the moment it sees one.
Ready to Practice?
"A Trie trades memory for speed — every prefix search is just an O(L) traversal away."