Lesson Tuesday

In this lesson, we will introduce the trie (pronounced "try"), which is a kind of tree that's often used for storing and retrieving strings. In fact, the word trie is associated with the "trie" in retrieval. We'll focus on the basics of what a trie is in this lesson. Then, if you like, you can do further research on your own to learn about how to add, remove, and find values in a trie.

A trie always has an "empty" root node with references to other nodes. Because of the references, it's not really empty - but the root node doesn't have a value on its own. It's common to use tries to store words, so if we were going to use a trie to store English words, we'd have a root node with 26 child nodes. Each child node would represent a letter of the alphabet.

This trie shows an empty root node plus the first three letters of the alphabet.

To simplify things, the trie above just shows the first three letters of the alphabet.

So what happens once we want to add actual words to a trie?

Each child node has a reference to each letter of the alphabet - just like the root node. So we'd construct words by adding more child nodes to the trie.

This trie includes the words "cat", "call", and "cot".

This trie now includes three words: cat, call, and cot. Each use the C node, which now has two child nodes to represent the three words we've added: an A node and an O node. Cat and call both use the C and its child A node. If we were going to add the word can, it would also use these two nodes before diverging.

The main advantage of tries is that they can retrieve strings very quickly. However, a significant disadvantage of tries is that they take a large amount of memory. Despite the memory issue, there are many important use cases for quick string retrieval. For instance, consider the autofill feature on search engines. A trie can be used to quickly determine possible substrings if a user has typed in the letters c and a. You can likely imagine many other use cases where quickly retrieving strings is important - ranging from the fields of genomics to data analytics.

If you'd like to learn how to create and search a trie yourself, check out the following article: Tries - JavaScript Simple Implementation.

Lesson 3 of 5
Last updated more than 3 months ago.