Imagine your computer's file system. You don't dump every file into a single folder and search linearly when you need something. Instead, you organize: /documents/work/reports/q4.pdf. The path itself narrows the search. Each folder you enter eliminates everything that doesn't belong.

Now picture a HashSet holding 10,000 words. Someone asks: "give me every word starting with pre." The hash function scattered those words across memory — predict is nowhere near prepare. You have no choice but to scan all 10,000 entries, checking each prefix character by character.

Do that for 100 different prefix queries and you're at a million comparisons. The data structure that gives you O(1) exact lookup is useless for partial matches because hashing destroys the relationships between similar keys.

What if, instead of hashing away the structure, you preserved it? What if the prefix itself was a walkable path — like navigating folders — where each character you follow eliminates every word that doesn't share that prefix?

Try it yourself — type a word below and watch the trie grow character by character. Notice how characters that already exist in the tree are free. Adding "cart" after "car" costs just one node.

That's the core idea behind a trie. Not a lookup table with a tree shape bolted on. A structure where the arrangement of the data IS the search.

Here's your challenge: six words need to enter a trie, but you have a limited node budget. Every character in a word needs a node — unless that node already exists from a previous insertion.

What happens when you insert words that share a common beginning? How many nodes does each new word actually cost? And does the order you insert them matter?

You have six words and a fixed budget — tight enough that a careless ordering will run out of nodes before all six words are placed. Some pairs of words look suspiciously similar. Others share nothing. Can you find an order that fits them all?

Watch the node counter as you place each word. Some insertions will barely move it. Others will spike it. Pay attention to when each happens — the pattern will tell you something important about how tries store data.

Notice what happened as you inserted words that share prefixes. car, card, care, and cart all share the path c → a → r. Four words, but only three shared nodes. Each new word after car only paid for its unique suffix — a single character. That's prefix compression, and it happens automatically whenever words share beginnings.

This is what makes a trie fundamentally different from a hash table. In a hash table, car and cart are strangers — hashed to unrelated slots. In a trie, they're neighbors. They share a home. And that shared structure is exactly what makes prefix queries trivial.

To find every word starting with car, you walk three nodes: c → a → r. Then you collect everything in the subtree below. No scanning. No filtering. No comparing against words that start with b or d or z. The irrelevant words were never on your path to begin with.

The cost is O(L) where L is the prefix length — and notice that this doesn't depend on the total number of words. Whether the trie holds the 6 words you just inserted or the entire 600,000-word English dictionary, walking c → a → r still takes exactly 3 steps. The trie scales with the length of what you're looking for, not the size of what you're looking through.

Scrub through a prefix query below. At each step, notice how many words get eliminated — not by comparing against them, but by simply not walking their branch.

That's the inversion worth remembering: the dictionary itself became the index.