The Trie Data Structure

An Interactive Explanation

A Trie (pronounced "try") is a tree data structure that is used to store Strings. It's generally used to search and store by prefix, which is why it is also known as a "prefix tree."

Tries can often come up in software engineering interviews, however they aren't generally taught in a typical Data Structures course. Like all data structures, they're often better understood by interacting with them.

This guide will feature written explanation, code samples, and interactive working Tries. You can find the code for the guide itself on Github, along with it's implementation of a Trie in Javascript.

This guide was made by @FlaqueEau to help out members of the Gonzaga University Makers and Developers club and the greater dev community. If you find something wrong or want to add more, we'd love to merge your pull request!

Basic Functions of a Trie

Insert()

The insert method of a Trie works by taking string and progressively taking each letter. The first node is generally empty, but for the purposes of explaination, we've labeled it as "root" in the demo below.

Pseudocode

  def insert(word):

    # Step 1: Grab the first letter of the word.
    firstLetter = word[0]

    # Step 2: Check if this letter already exists in
    #         our children at this node.
    if not this.children[firstLetter]:
      this.children[firstLetter] = new Trie()

    # Step 3: Pop off the first letter, then recurse.
    word = word.removeFirstLetter()
    this.children[firstLetter].insert(word)
       
Demo
<root>

Find()

The find method of a Trie works in the same way that most other tree structures work. Take the first letter of the word you're looking for and see if that exists as a child node. If it doesn't, you can stop, as that word does not exist in the Trie. Otherwise, find the node with that letter and search it's children for the next lettter. If you've run out of letters, then you've your item.

Pseudocode

  def find(word):

    # Step 1: Do a check to see we've found the node
    if isEmptyString(word) return true;

    # Step 2: Check to see if we've hit a letter that's not
    #         in the children of the current node
    const firstLetter = word[0];
    if not this.children[firstLetter]:
      return false;
    else:

      # Step 3: Pop off the first letter and continue searching
      word = word.removeFirstLetter()
      return this.children[firstLetter].find(word)
      
<root>rcrarecaratragrepcat