Shared Prefixes, Shared Paths

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.

A naive data structure stores each word independently, repeating "p-r-e" thousands of times. A trie does something elegant: it stores the prefix once.

This 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.

Let's state the principle precisely and then explore its implications:

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).

This is not a design choice—it's a mathematical consequence of how tries are constructed. When you insert a string into a trie, you:

1. Start at the root
2. For each character, follow the corresponding edge if it exists, or create it if it doesn't
3. After the last character, mark the node as an end-of-word

The 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.

Why this matters:

This sharing has profound implications:

1. Space efficiency: No redundant storage of common prefixes
2. Query efficiency: Navigating to any prefix automatically positions you to find all words sharing that prefix
3. Natural grouping: Words with common prefixes cluster together in the structure
4. Implicit hierarchy: Shorter words are prefixes of longer related words

Let'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.

Pay close attention to which nodes and edges are reused.

Let's visualize the final trie structure. I'll use ASCII art to show how paths merge and diverge:

                    [root]
                    /    
                   c      d
                   |      |
                   a      o*     ← 'do' ends here
                  / \\      |
                 t*  r*    g*    ← 'cat', 'car', 'dog' end here
                    / 
                   d*  e*        ← 'card', 'care' end here
                       |
                       f
                       |
                       u
                       |
                       l*        ← 'careful' ends here

Key structural observations:

The compression is dramatic:

The 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.

Let's trace a prefix query: "Find all words starting with 'car'"

Step 1: Navigate to prefix

root → 'c' → 'a' → 'r'

We're now at the node representing the prefix "car".

Step 2: Collect all words in this subtrie From this node, we can reach:

• This node itself (if end-of-word) → "car" ✓
• Path to 'd' (end-of-word) → "card" ✓
• Path to 'e' (end-of-word) → "care" ✓
• Path to 'e' → 'f' → 'u' → 'l' (end-of-word) → "careful" ✓

Result: {car, card, care, careful} — exactly the words with prefix "car"!

Complexity analysis:

For prefix query with prefix P of length p, returning k matching words:

1. Navigate to prefix node: O(p) — follow p edges
2. Enumerate subtrie: O(total characters in results) — proportional to output size

Total: O(p + output size)

Compare this to scanning all n strings:

The 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.

Definition: Longest Common Prefix (LCP)

For strings s₁ and s₂, the longest common prefix LCP(s₁, s₂) is the longest string that is a prefix of both.

• LCP("car", "card") = "car"
• LCP("cat", "car") = "ca"
• LCP("dog", "car") = "" (empty)

The Sharing Theorem:

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:

For a set of strings S = {s₁, s₂, ..., sₙ}, the node count of their trie is:

nodes = 1 + (total edges) = 1 + (sum of unique character positions across all strings)

More intuitively: every unique (prefix, next-character) pair creates one edge.

If "car" and "card" are in S:

• "car" contributes pairs: ("", c), (c, a), (ca, r) → 3 edges
• "card" contributes: ("", c), (c, a), (ca, r), (car, d) → but first 3 already exist! Only 1 new edge

Total edges for {car, card}: 4 (not 7) Total nodes: 5 (edges + 1 for root)

An important nuance: a word can be a prefix of another word, and tries handle this naturally.

Consider "car" and "card":

• "car" is a complete word
• "car" is also a prefix of "card"

The 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").

This is crucial for correctness:

The general pattern:

Every 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.

Stored words: {a, an, ant, antenna}

Path: root → a* → n* → t* → e → n → n → a*
                ↑     ↑    ↑               ↑
            end-of-word markers

• 'a' node: end-of-word (for "a")
• 'n' node: end-of-word (for "an")
• 't' node: end-of-word (for "ant")
• 'e', first 'n', second 'n' nodes: NOT end-of-word
• final 'a' node: end-of-word (for "antenna")

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.

Compression ratio:

compression_ratio = (total_characters_in_all_strings) / (number_of_trie_edges)

A ratio of 1 means no compression (no shared prefixes). A ratio of 10 means 10× compression (heavy sharing).