Howdy Reader 👋🏽

It's the 1990's and you've just come up with a brilliant idea! What if I built a sort of "search engine" for internet users to discover sites and named it Foogle? You build the engine but users don't know what to search. To make matters worst, the majority of users are spelling things wrong causing skewered results.

You decide to build an autocomplete to mitigate both issues. Luckily, you remember your college course on algorithms and data structure and the Trie data structure pops into your head.

Today, we are going to implement the autocomplete feature for your company Foogle using the trie data structure.

Here is a demo and source:

Prerequisites

• Basic knowledge of React and hooks.
• Basic understanding of data structures.
• Proficient in JavaScript.

What is Autocomplete 🤔

Autocomplete is a search engine feature where the search engine predicts the user's search and provides suggestions.

Project Design ✏️

Our project is a search engine whose functionality is exposed through a search bar. When a user types into the search bar, a back-end call is made for autocomplete suggestions based on the search query.

In the back-end, the user's search query is treated as a prefix used to find suggestions with the same prefix. The gathered sentences are lexicographically sorted (to make them easier to read) and returned to the front end.

The front-end displays the autocomplete results to the user.

Building the Front-End 🖥️

I'm not gonna spend too much time on this section because it's not the meat and potatoes of this article. I will, however, go over the parts that matter.

The main files to focus on are: App.js and SearchBar.js.

SearchBar.js contains the code for the search bar component, the "Foogle Search" and "I'm feeling lucky" buttons, and autocomplete results wrapper.

const SearchBar = (props) => {
  // Check if we have any autocomplete results
  const hasSearchResults = props.autocompleteResults.length > 0;

  return (
    <>
      <input type="text" onChange={(e) => {
        if (props.handleOnChange) {
          props.handleOnChange(e);
        }
      }} value={props.searchQuery} />
      </div>
      { /* Display autocomplete results */ }
      {
        props.autocompleteResults.map((autocompleteResult) => {
          return <li>autocompleteResult</li>;
      }
    </div>
  </>

It consumes three props:

• props.handleOnChange - Method to call when the input element is changed.
• props.searchQuery - Value to fill the input.
• props.autocompleteResults - Values to fill the autocomplete.

Controlled Component 🎛️

The handleOnChange and searchQuery props convert the input element into a controlled component. HTML form element usually maintains their own state which goes against React's methodologies.

In response, we set a hook as the single source of truth which is passed as the value for the input. A method is passed to handle the onChanged event for the input and updates the hook containing the input's value whenever the input is changed. This ensures that React stays in control.

// Hook representing the value of the input
const [value, setValue] = useState("");

const handleInputChange = (e) => {
  // Get value from the change
  const inputValue = e.target.value;

  // Update the hook to new value
  setValue(inputValue);
}

// Pass value and onChange handler
return <input value={value} onChange={handleInputChange} />

App.js is the main point of the code. It contains the Foogle home page, the search bar component and it's hook, and makes the call for autocomplete results.

const App = () => {
  // The value of the search bar
  const [searchQuery, setSearchQuery] = useState("");
  // The hook to retrieve autocomplete results using "searchQuery"
  const autocompleteResults = useAutocomplete(searchQuery);

  // The onChange handler for the search input
  const handleSearchInputChange = (e) => {
    setSearchQuery(e.target.value);
  }

  return (
    {/* Pass hook value, onChange handler, and autocomplete results */}
    <SearchBar searchQuery={searchQuery} handleOnChange={(e) => {
        handleSearchInputChange(e);
    }} autocompleteResults={autocompleteResults} />
  );
}

Designing The Autocomplete System 🏗️

The autocomplete results come from the useAutocomplete hook shown in App.js. Here's a look into the hook.

const useAutocomplete = (searchQuery) => {
  // Holds autocomplete results
  const [autocompleteResults, setAutocompleteResults] = useState([]);

  // Run when 'searchQuery' changes
  useEffect(() => {
    // If the search query is a valid string, fetch suggestions
    if (searchQuery.trim().length > 0) {
      // TODO Fetch suggestion from database
      // setAutocompleteResults();
    } else {
      // Clear autocomplete results on empty search query
      setAutocompleteResults([]);
    }
  }, [searchQuery]);

  // Return autocomplete results
  return autocompleteResults;
}

Let's pretend we have a database full of autocomplete suggestions. suggestionsDatabase.js represents this database.

const suggestionsDatabase = [
  "How to get a job at Google",
  "How to get gum out of hair",
  "How to get people to like me",
  "How to get a job at Amazon",
  "Sasuke is a trash character",
  "How high is the empire state building",
  "Her by Tyler The Creator"
  ...
];

When users type a search query, we have to find all suggestions that start with the query. The problem is how can we filter through all suggestions without checking each string one by one? Individually checking is extremely slow and has a time complexity of O(n) where n is the number of suggestions.

What if we had millions of suggestions? A search could end up with an O(10^9) time complexity. That would take hours or potentially days to run. Not to mention the millions of Foogle users hitting the database at the same time. We would have a terrible user experience! Luckily, we have the Trie data structure that's made to solve this very problem!

What is a Trie 🌳

A trie or prefix tree is a tree data structure made for quick retrievals of stored keys. In our case, our trie will store suggestions. Each node represents a letter in the alphabet and inside each node contains a Map that maps letters of the alphabet to other nodes which continue the cycle.

Here is the structure for a node.

class TrieNode {
  // Map for mapping letters to other child nodes
  children
  // Is this node the end of a string
  isEndOfString

  constructor() {
    this.children = new Map();
    this.isEndOfString = false;
  }
}

A node contains a Map for mapping letters to other child nodes and a boolean to indicate this node is the last letter of a string. Below is a visual representation of a trie.

Starting from the root, traversing down each branch node creates a representation of a string. A string is inserted into a trie letter by letter and each letter represents a level down in the trie.

For example, take the string there from the image above. Start with the first letter t and the root node. Check the root node's children for a mapping for the letter t to a child node. If it doesn't exist, create it and move to it. If it does, then move to it.

Now we are in a child node in the next level of the trie. We take the next letter h and repeat the process again. If the current node's children contain a mapping for h move to it, if not, create it and move to it. We move on to e and repeat the process till we get to the last letter e. We set isEndOfString true on the current node to indicate we ended a string on this node.

Code speaks louder than words so let's write some. Here is the code for the trie.

class Trie {
  rootNode

  constructor() {
    // Create root node
    this.rootNode = new TrieNode();
  }

  // Returns if the trie contains a string
  contains = (str) => {

  }

  // Inserts a string into the trie
  insert = (str) => {

  }

  // Get all words with prefix
  getWords = (prefix) => {

  }
}

Let's fill in the trie functions starting with insert since we went over the process.

Inserting a string

To recap inserting a string, start from the root node. Traverse down a child node for each letter in the string and mark the final node as isEndOfString.

insert = (str) => {
  // Convert to lower case so we don't have to worry
  // about case differences.
  str = str.toLowerCase();

  // Get the length of the string, so
  // we know how many levels to traverse.
  const length = str.length;

  // The crawl node for traversing the trie.
  let crawlNode = this.rootNode;

  // Loop for each char in the string.
  for (let level = 0; level < length; level++) {
    // Get the current char
    const char = str.charAt(level);

    // Check if the current node has a mapping
    // of the current char to a child node.
    // If not, create a node and map it.
    if (!crawlNode.children.has(char)) {
      crawlNode.children.set(char, new TrieNode());
    }

    // Traverse to the next mapped node in the trie.
    crawlNode = crawlNode.children.get(char);
  }

  // Set the current node as the end of the string.
  crawlNode.isEndOfString = true;
}

The time complexity is O(n) where n is the length of the string being inserted.

Searching a string

Searching if the trie contains a string is a similar process to insertion. We traverse the levels of the trie for each char in a string. If we encounter a node without a mapping of the current char, then the trie doesn't contain the string.

If we fully traverse a string and the final node doesn't have isEndOfString set as true, then the string isn't in the trie.

contains = (str) => {
  // Convert to lower case so we don't have to worry
  // about case differences.
  str = str.toLowerCase();

  // Get the length of the string, so
  // we know how many levels we need
  // to traverse.
  const length = str.length;

  // The crawl node for traversing the trie.
  let crawlNode = this.rootNode;

  // Loop for each char in the string.
  for (let level = 0; level < length; ++level) {
    // Get the current char
    const char = str.charAt(level);

    // If the current node doesn't have a mapping
    // for the current char, the string hasn’t
    // been inserted.
    if (!crawlNode.children.has(char)) {
      return false;
    }

    // Traverse to the next mapped node in the trie.
    crawlNode = crawlNode.children.get(char);
  }

  // Return if the current node
  // is the end of the string.
  return crawlNode.isEndOfString;
}

The time complexity for insertion is O(n) where n is the length of the string being inserted.

Retrieving all words with a prefix

Our problem was searching for autocomplete suggestions that have the same prefix as the user's search query. The trie solves our problem by efficiently storing autocomplete suggestions and allows us to quickly search them all at the same time because strings with the same prefix overlap the same nodes.

We are now going to create a method to retrieve all words from the trie that start with a prefix.

This is gonna be complex so pay attention. Imagine we have the strings below inserted in a trie.

is water blue
is fire hot
is sasuke trash

A user types the search query is which is a prefix to all three strings above. To find all words with the prefix of is, we need the child node of the last char in the prefix. In our case, we need the node for the s char when traversed from the root node with the i char.

Once we have the prefix node, we create a recursion function to build strings for each child node and their child nodes till we run out of nodes. Confused yet? It's easier to explain with code.

First, we need the node of the last char in the prefix. Let's add a parameter to the contains function to return the node instead of a boolean.

contains = (str, returnNode) => {
  // Convert to lower case so we don't have to worry
  // about case differences.
  str = str.toLowerCase();

  // Get the length of the string, so
  // we know how many levels we need
  // to traverse.
  const length = str.length;

  // The crawl node for traversing the trie.
  let crawlNode = this.rootNode;

  for (let level = 0; level < length; ++level) {
    const ch = str.charAt(level);

    if (!crawlNode.children.has(ch)) {
      return false;
    }

    crawlNode = crawlNode.children.get(ch);
  }

  // Return the current node
  if (returnNode) {
    return crawlNode;
  }

  return crawlNode.isEndOfString;
}

With the prefix root node, we can create the boilerplate for our getWords function.

  // Get all words with prefix
  getWords = (prefix) => {
    // Get root node of prefix
    let prefixRootNode = this.contains(prefix, true);

    // The prefix isn't in the trie.
    if (!prefixRootNode) {
      return [];
    }

    // Hold the results
    let result = [];

    // Call our recursion function from the prefix root.
    this.#_getWordsHelper(prefixRootNode, prefix, result);

    // Sort and return the results
    return result.sort();
  }

  // Recursion function to get all words that start from
  // node.
  #_getWordsHelper = (root, currString, result) => {

  }

To get all strings stored from a node, we use DFS recursion on every child node inside the current node we are on and repeat the process on it's child nodes.

Here's how it works. When _getWordsHelper is called, it checks if the current node is null, if so we ran out of nodes for the branch and stop; This is a base case.

#_getWordsHelper = (root, currString, result) => {
  // Base case: root null
  if (root === null) {
    return;
  } 
}

Next, it checks if the current node has isEndOfString set. If so, it add currString to the result array since it represents a complete string.

#_getWordsHelper = (root, currString, result) => {
  // Base case: root null
  if (root === null) {
    return;
  } 

  // Add word to result if we complete a string
  if (root.isEndOfString) {
    result.push(currString);
  }
}

Next, it takes every child node of the current node and calls itself on each of them, using the child node as the new root while appending the char the child node maps to onto currString for the new call to continue building the string.

#_getWordsHelper = (root, currString, result) => {
  // Base case: root null
  if (root === null) {
    return;
  }

  // Add word to result if we complete a string
  if (root.isEndOfString) {
    result.push(currString);
  }

  // Loop over each mapping in the children
  for (let [key, value] of root.children) {
    // Append the key char to 'currString' and
    // recur on the new node.
    this.#_getWordsHelper(value, currString + key, result);
  }
}

Following this process will eventually store every single string contained in trie that starts from the prefix root node. The full code for getWords is:

// Get all words with prefix
getWords = (prefix) => {
  // Get root node from prefix
  let prefixRootNode = this.contains(prefix, true);

  // The prefix isn't in the trie.
  if (!prefixRootNode) {
    return [];
  }

  // Hold the results
  let result = [];

  // Call our recursion function from the prefix root.
  this.#_getWordsHelper(prefixRootNode, prefix, result);

  // Sort and return the results
  return result.sort();
}

// Recur on the children of the current node
// and add any complete strings to the result
// array.
#_getWordsHelper = (root, currString, result) => {
  // Base case: root null
  if (root === null) {
    return;
  }

  // Add word to result if we complete a string
  if (root.isEndOfString) {
    result.push(currString);
  }

  // Loop over each mapping in the children
  for (let [key, value] of root.children) {
    // Append the key char to currStirng and
    // recur on the current node.
    this.#_getWordsHelper(value, currString + key, result);
  }
}

The time complexity for getting all prefixes is O(n) where n is the number of nodes in the trie.

Connecting our suggestions database

To represent the autocomplete suggestions database, we insert all the suggestionsDatabase strings into the trie. Let's add a constructor to Trie that accepts strings and inserts them into itself.

class Trie {
...
  constructor(strs) {
    this.rootNode = new TrieNode();

    // Insert strings into the trie.
    strs.forEach((str) => {
      this.insert(strs);
    });
  }
...
}

Going back to the front-end and inside the useAutocomplete.js file. Before the class declaration, init the Trie class and pass the suggestionsDatabase strings. This will function as our pseudo suggestions database.

import { suggestionsDatabase } from "./suggestionsDatabase";

// Pretend we connected to our database.
const trie = new Trie(suggestionsDatabase);

const useAutocomplete = (searchQuery) => {
...

Now inside the useEffect method, we add code to retrieve all words with the searchQuery as a prefix from the trie.

const trie = new Trie(suggestionsDatabase);

const useAutocomplete = (searchQuery) => {
  // Holds autocomplete results
  const [autocompleteResults, setAutocompleteResults] = useState([]);

  // Run when 'searchQuery' changes
  useEffect(() => {
    // If the search query is a valid strings, fetch suggestions
    if (searchQuery.trim().length > 0) {
      // Fetch suggestion from database
      setAutocompleteResults(trie.getWords(searchQuery));
    } else {
      // Clear autocomplete results on empty search query
      setAutocompleteResults([]);
    }
  }, [searchQuery]);

  // Return autocomplete results
  return autocompleteResults;
}

Typing into the search bar will return all autocomplete suggestions that share a common prefix with the search query!! 😁

Final Thoughts 💭

We created a search bar input and maintained its state with a hook. We have mullions of autocomplete suggestions to filter when a user searches. In response, we construct a trie to store suggestions that can easily be retrieved for an O(n) time complexity instead of an (10^9) time complexity.

The trie solves our problem by efficiently storing autocomplete suggestions and allows us to quickly search words with the same prefix because strings with the same prefix overlap the same nodes. When a search query is entered, we retrieve all autocomplete suggestions that are prefixed with the query and show them to the user!

About Me 👨🏽‍💻

I'm Gregory Gaines, a fun-loving software engineer @Google who loves writing entertaining articles. If you want more content, follow me on Twitter at @GregoryAGaines.

After reading this maybe you should apply to Google 😆! If you have any questions, hit me up on Twitter (@GregoryAGaines).

Legal: I am a Google employee; all opinions are my own. This post is not an endorsement nor contains any proprietary knowledge.