Trie Data Structure
Recently I participated in a job interview that required me to have working knowledge of the Trie Data Structure; needless to say having never worked with one these before…. it did not go so well. So this week I thought I take dive into this type of data structure, look at what are some good use cases and how to implement one in code.
Whats it all About?
A Trie Data Structure, also referred to as a digital tree or prefix tree, is a type of search tree, used to locate specific strings key within a set. This type of data structure is idea for the retrieval of words with-in a tree, hints the name trie. Alright, now that we understand whats its all about, lets take a look at how it works. Below is an example of a trie tree.
Hows it work?
Lets say your looking to create an auto-complete function in your application, allowing your users to arrow down or click on a word that which prefix has been typed in the search box, here enters Trie. Tries are great for this type of storage because it allows you to create a prefix like shown above with common letters on a node path(above prefix — RO), and then once the word you are searching no longer matches the next node, you simply split off down a separate node path. This makes it idea for auto-complete, search, spell checkers or even sort!
Give Me The Code!
Alright lets put we learned into some code, JavaScript to be exact. Simply to use a GIF illustrating a TRIE autocomplete, I will use the the words used.
First, we will go ahead and set a group of words we want to filter in our search box to a constant, aswell as create are search and event listener…
const words = ['great','tea','ten','teddy','movie','moon'];document.getElementById('search').addEventListener('input', (e) => {
.....
}
Next we will go ahead and setup are array to filter the letters being inputted, converting those letters to lowercase and then using those letters in order to find similar prefixes(our auto-complete at work)…
let wordsArray = [];if(e.target.value){
wordsArray = words.filter(word => word.toLowerCase().includes(e.target.value))
wordsArray = wordsArray.map(word => `<br>${word}<br>`)
}
....
Lastly, we will implement a way to see the words being filtered by their prefixes…..
function showWordsArray(wordsArray){
const html = !wordsArray.length ? '' : wordsArray.join('')
document.querySelector('ul').innerHTML = html
}all together we should get something like this…
const words = ['Great', 'Tea', 'Ten', 'Teddy', 'Movie', 'Moon'];document.getElementById('search').addEventListener('input', (e) => {let wordsArray = [];if(e.target.value){
wordsArray = words.filter(word => word.toLowerCase().includes(e.target.value))
wordsArray = wordsArray.map(word => `<br>${word}<br>`)
}showWordsArray(wordsArray);
});
function showWordsArray(wordsArray){
const html = !wordsArray.length ? '' : wordsArray.join('')
document.querySelector('ul').innerHTML = html
}
Conclusion
This is a very basic example of using a Trie Data-Structure, at best it shows how we can go about creating a way to filter thru known prefixes. Below I listed a video to Traversy Media, my personal favorite youtuber for tutorials, besides Programming with Mosh, that gives a more in-depth way of using auto-complete with JavaScript and JSON.
Happy Coding!
