Why Trie?

Christopher Diep
2 min readNov 12, 2018

You autocomplete me!

“four people giving high fives at the same time” by rawpixel on Unsplash

A trie (also known as a prefix tree) is a kind of tree data structure composed of nodes. Generally, each node would have an character or an empty value to represent the end of the path. It looks something like this (when there’s no empty node):

Source: https://www.topcoder.com/community/competitive-programming/tutorials/using-tries/

It is useful for the implementation of an autocomplete feature because it effectively narrows down the number of possibilities whenever a longer input (or prefix) is used to look through the trie. It is a more efficient lookup compared to a hash table and can offer suggestions for typos.

Word Games: Scrabbled & Boggled

“Scrabble game with lawyer and probate word” by Melinda Gimpel on Unsplash

I heard about this data structure when attempting to solve a problem on Collabedit during a technical phone interview. The use case is to check possible matches on a Boggle board. Whenever there is a need to validate a string as a word, consider using trie. (I will next time.)

A hash table could have worked but it became hectic when I started to go through strings of various lengths.

When Implementing

Whenever implementing a trie in a language, it would be good for the code to include functions to:

  • insert a word
  • find a word
  • delete a word

Conclusion

A trie is a rare data structure that people can run into. However, it is nifty how people have used it to create an autocomplete. It’s nice whenever you make a friend who can complete your sentences.

Additional sources

--

--