A Crash Course in Tries

Trie, Trie, Trie again!

Dictionaries, a common trie application

Audience

This article is aimed at developers with a working knowledge of trees (you can swot up on my article here). It gives a quick overview of tries and their applications, then concludes with a worked example of a tries-orientated problem.

Argument

Tries are a type of tree data structure, it contains nodes, edges, a root, and parent-child relationships. However, a trie acts as a key-value data store. The key is always a string, but the value can be anything. In fact, the value can be nothing at all! Tries can also be used to store a unique list of keys.

Let’s explore this concept with an example.

A dictionary of last names to first names

In the above diagram we have a trie for storing dictionaries of last names to first names. We can see it contains a single last name (Smith), and a single first name (John). Let’s add another two people, Jane Smith and Agon Smakaj.

Adding more names to our trie

We share the first two letters of the key, and from there branch out. It’s reasonably easy to see how this can be expanded into other applications.

One common use of this pattern is for primary keys in data stores. Additionally we may use it to search values by a prefix. If we were looking for names of people with last name beginning ‘Sm’, we could use this structure to retrieve all three of our entries. Often as tries expand we will limit these retrievals to a set number, say the first m.

Hybrid Tries

From the previous diagrams we may notice that this structure is most useful when our keys share a lot of common letters. If this is not the case then our tree becomes too spread out and stops being helpful.

To circumvent this issue we may use a hybrid structure.

Using a hybrid structure to incrementally expand trees

We set a threshold for our tree, and continue adding strings to a node until we reach this threshold. At this point we expand the node to a more traditional tree structure and carry on as before.

Employing Tries

This problem is taken from LeetCode and is formulated as follows

In English, we have a concept called root, which can be followed by some other word to form another longer word — let’s call this word successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Imagine we are provided a dictionary of words: bat, cat and rat. We can expand this into a trie below (forgive the double use of root).

A dictionary as a trie

To find the shortest root of a successor we recurse down the tree, matching up letters until we reach the end of a branch. This is our root. If there is no match for a starting letter then there exists no root (fat, for example, would not match anything).

We have a solution below

Conclusion

In conclusion, we have covered tries, their properties and concluded with a worked example.