About

A trie (pronounced "try") is a data structure that allows for a search algorithm with a logarithmic time complexity. If that was too much computer science jargon, just know that searching the trie is very fast. How fast exactly? Try this metaphor: Imagine I gave you a list a of 10,000 words in a random order.

If I then told you to find the word scholar, you would have no idea where to start. Your best method is to probably scan the entire list from the beginning word for word until you find scholar. This method is inefficient and rather tedious. Computers don't mind tedium, but inefficiency can be a problem. This is where a trie comes into play.

Imagine that I give you the word and on a piece of paper and tell you to put it inside of a magic folder. Once you open the folder, you're surprised to find 26 other folders, labeled A through Z. Since our word is and, we put it into the A folder. But once we open the A folder, we find that there are another set of folders labeled A through Z. What folder do we put our word into now?

Since we already are in the A folder, it doesn't make sense to put this word into another A folder. Instead, we move on to the second letter of and, N! But as you might have guessed, inside the N folder, we have another set of A through Z folders. With one letter left, we move into the D folder. Once we open the D folder, there are another set of A through Z folders. But at this point, we have run out of letters, so we put our word inside the front of the D folder, and don't nest it any further. The path looks like this: Magic Folder > A Folder > N Folder > D Folder.

When you click on the populate trie button below, each word in the 10,000 list I gave you earlier is placed into the magic folder. Now if I ask you to find the word scholar, it's much easier. You start by opening the S folder. Within that, you open the C folder. After that the H folder, and so on until you find the word scholar. Isn't this much faster than skimming the entire list?

To see just how much faster, take a look at the bottom right corner of the search results. Each time you type into the search bar, a trie search (magic folder method) and a linear search (scanning the entire list) are conducted and timed. See for yourself the difference!

This feature works best if you are using Google Chrome. When measuring performance, Safari and Firefox round up to the nearest millisecond whereas Chrome will measure up to 10 decimal places. At least a few decimal places are needed to measure the performance of these functions.