101
0/276
Loading content...
Consider the English dictionary. It contains thousands of words starting with "pre-": precise, predict, premium, prepare, present, preserve, prevent. Each word is unique, yet they all share a common beginning.\n\nA naive data structure stores each word independently, repeating "p-r-e" thousands of times. A trie does something elegant: it stores the prefix once.\n\nThis single principle—shared prefixes lead to shared paths—is the engine that drives everything a trie can do. It's why tries are space-efficient for overlapping data, why prefix queries are fast, and why the structure naturally organizes strings by their common beginnings.
By the end of this page, you will understand exactly how multiple strings merge onto shared paths in a trie, how this sharing affects storage and retrieval, and how to visualize the overlay process. You'll see that this isn't just an optimization—it's the defining characteristic that makes tries unique.
Let's state the principle precisely and then explore its implications:\n\n> If two strings share a prefix of length k, their paths through the trie share exactly the first k edges and k+1 nodes (including the root).\n\nThis is not a design choice—it's a mathematical consequence of how tries are constructed. When you insert a string into a trie, you:\n\n1. Start at the root\n2. For each character, follow the corresponding edge if it exists, or create it if it doesn't\n3. After the last character, mark the node as an end-of-word\n\nThe key insight is step 2: you follow existing edges when they exist. Two strings that start with the same characters will follow the same edges for those characters.
Consider strings "car" and "card":\n\n• "car" creates path: root → c → a → r (mark end-of-word)\n• "card" follows: root → c → a → r (already exist!) → d (create, mark end-of-word)\n\nThe path c→a→r is shared. The 'd' extends it. "car" is both a complete word AND a prefix of "card"—the trie naturally represents both relationships.
Why this matters:\n\nThis sharing has profound implications:\n\n1. Space efficiency: No redundant storage of common prefixes\n2. Query efficiency: Navigating to any prefix automatically positions you to find all words sharing that prefix\n3. Natural grouping: Words with common prefixes cluster together in the structure\n4. Implicit hierarchy: Shorter words are prefixes of longer related words\n\nLet's see this concretely.
Let's build a trie inserting words one at a time and observe how paths merge. We'll insert the words: cat, car, card, care, careful, dog, do.\n\nPay close attention to which nodes and edges are reused.
Inserting 'cat' into empty trie:\n\n1. Start at root (empty trie)\n2. Character 'c': no 'c' edge from root → create node, add edge labeled 'c'\n3. Character 'a': no 'a' edge from current node → create node, add edge labeled 'a'\n4. Character 't': no 't' edge → create node, add edge labeled 't'\n5. End of word: mark current node as end-of-word\n\nResult: Path root → c → a → t* where * indicates end-of-word\n\nNodes created: 4 (root + 3 new nodes)\nEdges created: 3
Let's visualize the final trie structure. I'll use ASCII art to show how paths merge and diverge:\n\n\n [root]\n / \\\n c d\n | |\n a o* ← 'do' ends here\n / \\ |\n t* r* g* ← 'cat', 'car', 'dog' end here\n / \\\n d* e* ← 'card', 'care' end here\n |\n f\n |\n u\n |\n l* ← 'careful' ends here\n\n\nKey structural observations:
The compression is dramatic:\n\n| Metric | Without Sharing | With Trie | Savings |\n|--------|-----------------|-----------|---------|\n| Characters stored | 26 | 12 edges | 54% |\n| 'car' prefix repetitions | 4 times | 1 time | 75% |\n| 'care' prefix repetitions | 2 times | 1 time | 50% |\n\nThe savings compound with more words. A dictionary with 10,000 'pre-' words stores p→r→e exactly once, not 10,000 times.
Here's where the magic happens. Because words with a common prefix share a path, navigating to the end of that path positions you at the root of a subtrie containing exactly those words.\n\nLet's trace a prefix query: "Find all words starting with 'car'"\n\nStep 1: Navigate to prefix\n\nroot → 'c' → 'a' → 'r'\n\nWe're now at the node representing the prefix "car".\n\nStep 2: Collect all words in this subtrie\nFrom this node, we can reach:\n- This node itself (if end-of-word) → "car" ✓\n- Path to 'd' (end-of-word) → "card" ✓\n- Path to 'e' (end-of-word) → "care" ✓\n- Path to 'e' → 'f' → 'u' → 'l' (end-of-word) → "careful" ✓\n\nResult: {car, card, care, careful} — exactly the words with prefix "car"!
Every node in a trie is the root of a subtrie containing all words that share the prefix represented by the path to that node. Prefix queries are just 'navigate to prefix node + enumerate subtrie'. The sharing property GUARANTEES that all matching words (and only matching words) are in that subtrie.
Complexity analysis:\n\nFor prefix query with prefix P of length p, returning k matching words:\n\n1. Navigate to prefix node: O(p) — follow p edges\n2. Enumerate subtrie: O(total characters in results) — proportional to output size\n\nTotal: O(p + output size)\n\nCompare this to scanning all n strings:\n\n| Approach | Time Complexity | For 1M strings, prefix 'car' |\n|----------|-----------------|------------------------------|\n| Linear scan | O(n × p) | ~3 million char comparisons |\n| Trie | O(p + k) | 3 steps + result traversal |\n\nThe trie's advantage grows with dataset size because navigation time is independent of n.
Let's formalize the sharing mathematically. This will help you predict trie behavior and analyze space complexity.\n\nDefinition: Longest Common Prefix (LCP)\n\nFor strings s₁ and s₂, the longest common prefix LCP(s₁, s₂) is the longest string that is a prefix of both.\n\n- LCP("car", "card") = "car"\n- LCP("cat", "car") = "ca"\n- LCP("dog", "car") = "" (empty)\n\nThe Sharing Theorem:\n\n> Strings s₁ and s₂ share exactly |LCP(s₁, s₂)| + 1 nodes in the trie, where the +1 is for the root.
Extending to multiple strings:\n\nFor a set of strings S = {s₁, s₂, ..., sₙ}, the node count of their trie is:\n\n\nnodes = 1 + (total edges) = 1 + (sum of unique character positions across all strings)\n\n\nMore intuitively: every unique (prefix, next-character) pair creates one edge.\n\nIf "car" and "card" are in S:\n- "car" contributes pairs: ("", c), (c, a), (ca, r) → 3 edges\n- "card" contributes: ("", c), (c, a), (ca, r), (car, d) → but first 3 already exist! Only 1 new edge\n\nTotal edges for {car, card}: 4 (not 7)\nTotal nodes: 5 (edges + 1 for root)
For a trie containing n strings with total length L and total unique (prefix, char) pairs U:\n\n• Number of nodes = U + 1\n• Number of edges = U\n• U ≤ L (equality when no prefix sharing)\n• U can be much smaller than L with heavy sharing\n\nBest case: n strings of length m, all starting the same → O(m) nodes\nWorst case: n strings with no common prefixes → O(L) = O(n × avg_length) nodes
An important nuance: a word can be a prefix of another word, and tries handle this naturally.\n\nConsider "car" and "card":\n- "car" is a complete word\n- "car" is also a prefix of "card"\n\nThe trie handles this seamlessly because end-of-word is a node property, not a structural property. The node at the end of path c→a→r is marked as end-of-word (for "car") AND it has a child 'd' (continuing to "card").\n\nThis is crucial for correctness:
The general pattern:\n\nEvery string creates a path. Only some nodes on that path are end-of-word nodes. Specifically, a node is end-of-word if and only if a stored string ends at that node.\n\n\nStored words: {a, an, ant, antenna}\n\nPath: root → a* → n* → t* → e → n → n → a*\n ↑ ↑ ↑ ↑\n end-of-word markers\n\n• 'a' node: end-of-word (for "a")\n• 'n' node: end-of-word (for "an")\n• 't' node: end-of-word (for "ant")\n• 'e', first 'n', second 'n' nodes: NOT end-of-word\n• final 'a' node: end-of-word (for "antenna")\n
How much space does a trie actually save? It depends entirely on how much your strings overlap. Let's develop intuition for when tries shine.\n\nCompression ratio:\n\n\ncompression_ratio = (total_characters_in_all_strings) / (number_of_trie_edges)\n\n\nA ratio of 1 means no compression (no shared prefixes). A ratio of 10 means 10× compression (heavy sharing).
| Data Pattern | Example | Approximate Ratio | Trie Benefit |
|---|---|---|---|
| Random strings | "xkq", "plm", "wvb" | ~1 | None (consider hash table) |
| Common suffix only | "running", "jumping", "sleeping" | ~1 | None (tries share prefixes, not suffixes) |
| Dictionary words | English word list | ~3-5 | Moderate |
| Common prefix family | "program", "programming", "programmer" | ~2-3 | Good |
| URL paths | "/api/v1/users", "/api/v1/posts" | ~5-10 | Excellent |
| IP addresses | "192.168.1.*" range | ~10+ | Excellent |
Data with high prefix overlap includes:\n• Words with common roots (un-, re-, pre-, anti-)\n• Hierarchical paths (URLs, file paths)\n• Structured identifiers (IP addresses, product codes)\n• Auto-generated sequences (log timestamps)\n\nData with low overlap: random hashes, UUIDs, encrypted strings, natural language text treated as single strings.
Here's a property that falls naturally out of the sharing structure: in-order traversal of a trie yields strings in lexicographic (alphabetical) order.\n\nWhy? Because the trie's structure mirrors the lexicographic ordering! At each node, if you visit children in alphabetical order (a before b before c...), you'll process shorter prefixes before their extensions, and you'll process 'aardvark' before 'apple' before 'zebra'.
The traversal algorithm:\n\n\nfunction collectAllWords(node, prefix, results):\n if node is end-of-word:\n results.add(prefix)\n for each child c in alphabetical order:\n collectAllWords(c, prefix + c.character, results)\n\n\nFor our example trie:\n\nVisiting children alphabetically from root:\n1. Visit 'c' subtrie first (before 'd')\n - Visit 'a' subtrie\n - Visit 'r' subtrie (before 't')\n - Found "car" (r is end-of-word)\n - Visit 'd' subtrie: found "card"\n - Visit 'e' subtrie: found "care"\n - Continue to find "careful"\n - Visit 't' subtrie: found "cat"\n2. Visit 'd' subtrie\n - Visit 'o' subtrie: found "do"\n - Visit 'g' subtrie: found "dog"\n\nResult: [car, card, care, careful, cat, do, dog] — lexicographically sorted!
Unlike hash tables (which have no inherent order) or BSTs (which require explicit balancing for sorted output), tries give you sorted iteration as a natural consequence of their structure. This is invaluable for autocomplete—suggestions come out alphabetically without additional sorting.
The principle of shared prefixes leading to shared paths is the heart of what makes tries powerful. Let's consolidate:
What's next:\n\nYou now understand how multiple strings overlay onto shared paths in a trie. The next page explores character-by-character navigation—the process of traversing a trie one character at a time, which is the foundation for insert, search, and prefix operations.
You've mastered the sharing principle: common prefixes create shared paths. This single insight explains trie space efficiency, prefix query speed, and natural sorted order. Next, we'll see exactly how to navigate these shared paths character by character.