Mr. Grummel Get the app
← All notes
LEARNING 5 MIN READ DRAFT — APRIL 2028

The tree structure that stores a whole dictionary by sharing every word's common beginning

A trie stores words by sharing their common prefixes in one tree structure, letting it answer does any word start with these letters instantly, without checking every word one at a time.

A trie stores a set of strings, a dictionary of words, say, by sharing every common prefix between them within a single tree structure, rather than storing each individual word as a completely separate, self-contained entry the way a plain list would. That shared-prefix structure is exactly what lets a trie answer whether any stored word starts with a given sequence of letters essentially instantly, without needing to check every single word in the whole set one at a time.

Words sharing a prefix share the same path through the tree before branching apart

Each node in a trie represents one character, and a path from the tree's root down through several nodes spells out a complete string. Words that share a common prefix share that same initial path through the tree before finally branching apart at the point where their letters actually start to differ, which is exactly what makes a trie's shared-prefix storage genuinely more space-efficient than storing every word as a fully separate string whenever a dataset happens to have a lot of overlapping prefixes among its entries.

That structure makes fast prefix lookups its single clearest practical strength

Autocomplete, spell-checking, and IP routing table lookups all rely on exactly this fast prefix-matching capability. A trie can confirm or rule out whether any stored word starts with a given prefix by walking only as many nodes as the prefix itself is long, regardless of how many total words the whole structure actually contains, a genuinely different, faster guarantee than checking a plain list of words one at a time would offer.

A trie stores a set of strings, a dictionary of words, say, by sharing every common prefix between them in one tree structure rather than storing each word as a completely separate, self-contained entry, and that shared-prefix structure is exactly what lets a trie answer does any word start with these letters instantly, without checking every word in the set one at a time.

What we're still unsure about

That a trie's shared-prefix structure enables fast prefix lookups is well established, uncontroversial computer science. What's genuinely worth flagging is that a plain trie can actually end up using more total memory than a simpler structure when the stored strings don't share many common prefixes with each other, since every node in the tree still carries its own storage overhead even within a mostly sparse, thinly branching structure, and picking a trie over a simpler alternative genuinely depends on how much prefix overlap the actual specific dataset in question has, not on prefix-matching speed alone.

This sits inside Tries & Suffix Structures, one of eight topics in Data Structures, one of seven domains in Computer Science, one of seventeen subjects the app can quiz you on.

Draft — not published yet.
Try the pop quiz