Trie Tree Meets React
Most software engineers encounter the need to create a form that takes in user inputs. There are many different variations of inputs, but the most common include things like a selection (dropdown), checkboxes, and text inputs. For the purposes of this article, we’ll be focusing on text inputs which are most commonly seen in places like a search bar. Search bars can arguably be one of the most important features of any website. Millions of people interact with it each day in places like Google and YouTube. However, while many people appreciate the functionality of a search bar, the second most common feature and what ties everything together may go unappreciated at a glance. The autocompletion. Being able to type a couple of words into Google and having it complete my desired search is easily one of the greatest inventions of all time, especially as a programmer who relies heavily upon Google to find answers to my questions.
The Problem
How can someone build an autocomplete feature like Google? Well, one approach would be to store the search terms in an array then display all the possible completions in the dropdown by comparing the user input to the values stored. That could work perfectly fine, but let's scale this to Google level size. Google has more than 1.5 billion active users and is responsible for handling millions of searches every day. If you were to store even a small fraction of these search phrases and words in something like an array. It becomes very inefficient because we need to read in all the words and phrases in the array then compare character by character each time. This is a very costly operation and we know from the success of Google that they probably don’t use these data structures for creating an autocompletion. However, they probably use something similar to what’s known as a trie tree.
A Trie What?
A trie or prefix tree (searched by prefixes) is a data structure that takes advantage of the keys it stores to share prefixes in order to speed up the completion. The tree is arranged where the word is stored along paths from the root down to the leaf nodes (last node) and the node’s position in the tree corresponds to the letter position of a given prefix. You may notice that the root is empty and that’s because we don’t know the first character of a given word. You could think of it like leaving a search bar empty, we’re not sure what we want to search.
Node properties
Common node properties include the character which represents the node, an underlying data structure like a dictionary to associate character keys to children node values, and a boolean to mark whether or not a string is terminal (the last character). You could add many more values such as giving it a weight property that you could use to count the frequency of a word the user types and based on the weight, display it to the user as a recommendation.
How it’s faster
If we recall the problem with storing words in something like an array the issues lie upon the lookup. We needed to compare each character in the input word with each character we have stored which is a very expensive operation when storing many words. However, a trie tree is extremely fast because the number of comparisons we make depends on the number of characters in a given word. The lookup efficiency of a trie tree comes from being able to jump directly to a node containing the character we’re looking for. Rather than having to traverse all the words in something like an array to find a matching prefix, a trie tree points directly to a node containing the character and proceeds to traverse down checking if each character in a given word exists as a child of the current node.
How I Implemented a Trie Tree
As you may have been able to guess, I implemented a trie tree by creating my own search bar with autocomplete using Typescript and React. But, why not just use any other library you may ask? Well, that’s a very valid point, but my goal was to further understand how to incorporate an uncommon data structure such as a trie tree into a real-world project. Not to mention, since I made it, I know the ins and outs of how everything is working, so if I use it for any future projects it’ll be a lot easier to add things I want and debug any issues.
Things I wanted to include
- Have the component easily customizable to fit the needs of any project.
- The ability to decide whether or not you want to load a corpus or build a tree as the user inputs words.
- Make sure the component was functional to the point where you don’t have to go in and make changes all the time like the placeholder, input type, disable submitting words to the tree, and retrieving the value within the component from a parent.
Building the component
After writing up the trie tree in Typescript, I started with the UI of my search bar first. My goal was to allow anyone to use this search bar in any project so I had to make the design easily interchangeable. To do this, I used something called styled-components. Styled-components allow you to write CSS inside a Javascript file with the added benefit of being able to use some Javascript functionality to help style your website. For example, being able to use ternary operators to make style decisions. More importantly, you don’t need to carry a separate stylesheet along with the component, it’s all in one file.
Another big feature I wanted to add was allowing a user to add a corpus. This would allow you to populate the tree with phrases and words easily without having to manually submit each word. Utilizing React’s prop system has made it even easier by eliminating the need to open the trietree.ts file and digging through it to add functionality. Quick aside for those who aren’t aware of what props are in React. Props (short for properties) is a way of passing information into a component. Think of it like passing function arguments. This allows you to easily add or exchange a corpus by adding the prop:
<SearchBar corpus={YOUR_CORPUS} />Lastly, I wanted to eliminate the need to open the component file for changing small things like the placeholder, input type, disable submitting words, and retrieving the value of the input from the component back to the parent. Again, utilizing React’s prop system has made it extremely for a user to configure the component.
<SearchBar placeholder="EXAMPLE" type="text" onChange={(text) => setText(text) disableTermSubmit />The cherry on top
What if someone doesn’t want to use my search bar with all the bells and whistles? Well, for those people I extracted the functionality into its very own React Hook! There’s no need to fully understand what React Hooks are, but simply put, it’s a function. Utilizing the autocomplete hook will allow the user to fully customize the functionality and build it how they want to, all while still being able to use the advantages of a trie tree. Simply import the hook along with the trie tree files and you’re all set. It’s as easy as:
const [completions] = useAutocomplete(searchTerm, optionalCorpus);The user supplies the search term which is used to find any matching prefixes along with the option to add a corpus to populate the tree. The hook returns an array of matching words or phrases and it’s up to the user to utilize the information.
Conclusion
As discussed earlier in the article, autocomplete helps the overall user experience when searching. Being able to input a couple of words then having an application make suggestions can save a user a ton of time over the long haul. There are also some other added benefits like preventing any spelling errors and informing a user what kind of response they’ll get from the dropdown menu.
If you would like to further explore and understand trie trees, I highly recommend reading an article by Vaidehi Joshi called “Trying to Understand Tries.” She explains everything you need to know about tries with visuals as well as discussing the time complexity of operations.
Interested in checking out my React autocomplete? Check out the repo!
