The ‘trie’ data structure gets a new name

Homonyms don’t make good technical terms

A trie is a subtype of the tree data structure that is helpful for indexing strings. But how to pronounce something spelled “trie” ?

The phonetics of “trie” are an abject quagmire. By remaining fully-ambiguated in normal conversation, the more pedantic among us can subtly test whether the listener understands just which tr*e is being referred to. Or worse, pronounce it as “try” and wait for your conversation partner to respond with, “tri- what?”

From Wikipedia:

The idea was independently described in 1960 by Edward Fredkin, who coined the term trie, pronouncing it /ˈtriː/ (as “tree”), after the middle syllable of retrieval.

This reasoning, while cute, makes absolutely no sense.

The trie data structure nomenclature has been an abomination for too long. Software Engineers love destroying legacy baggage and Chesterton’s gates, and in that spirit, today I’m announcing that what was formerly known as the trie is now called the prefix tree. Because the whole point is that it stores word prefixes as an index for the full word. Get it? Of course you do. It makes nothing but sense. Even wikipedia suggests it as an alternative to “trie”, so there you go.

Everybody’s got a story

Four years ago I interviewed at Google, and one of the interviews was a coding test. Following the test was a discussion about some existing code that I was asked to analyze. It was clearly an implementation of a prefix tree in Python. After I referred to it as “prefix tree” multiple times, the interviewer finally asked:

You’re talking about a trie, right? As in, T-R-I-E?

Yes I was, which I use to disambiguate between it and other types of trees, in the same way I might say “oak tree” instead of “troake”. Not everything needs its own special chimeric neologism. In any case, I went on to pass that interview, so I do have a somewhat special place in my heart for the mis-naming of trie.

But nostalgia should not override logic. And if you have to spell out a technical term phonetically like you’re broadcasting over ham radio, maybe it’s time to think about using a different name.

That new name is here. Stop calling it a trie, or T-R-I-E, or try: it’s called the prefix tree. Enjoy.