Why Trie?
You autocomplete me!
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):
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
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.
