My favorite data structure: Trie

Have you wondered how a search engine knows the next word or sentence you will type in the search bar? Well, the autocomplete feature is being handled by a Trie data structure behind the scenes. A Trie is a type of k-ary search tree used for storing and searching specific keys from within a set. Usually these keys are strings. To access a key, the Trie is traversed depth-first. Each node of a Trie represents a string and each edge represents a character with the root node being an empty string.

Here’s an example of the Trie data structure:

Trie Node Structure

A Trie node consists of the following:

• the character
• a marker to indicate a leaf node
• it’s children

Autocomplete Function

For the autocomplete function, you iterate through the Trie according to the prefix. Once the node which holds the last letter of the prefix is reached, we can use recursion to find all the nodes branched from the last node prefix. This is the same method as a pre-order traversal.

For example: when searching “amaz”, it should return all the words that start with “amaz” like “amazon”, “amazing”, etc.

Here’s an implementation of the autocomplete function using a recursive helper function:

Closing

So, now you know the mechanism behind the autocomplete function. In some cases, the Trie node can store the count of that prefix to keep track of popular words or sentences. There’s also insert functions and delete functions for Tries, but for this blog we talked about the Trie Node structure and the autocomplete function.

Hope you enjoyed!