Adam Zerner

Overview of tries

In my mind, the basic data structures are roughly:

Then after that you have data structures that I guess you can call intermediate:

Anything else I'd probably categorize as an "advanced" data structure. Stuff like:

Tries would fit under the umbrella of advanced data structures to me. There's some complexity you have to wrap your head around, and they aren't used very often.

If you're up for a challenge, let's dive into the topic of tries. We'll talk about what they are, when they're used and how they work. Don't worry, it's nothing too crazy.

Overview

Imagine that you want to store the words:

There are a lot of ways to do this. You can use an array. You can use a hash.

Or, you can store them like this:

That's how a trie would store them. A big advantage to storing it this way is because it allows you to do stuff with word prefixes. (They're also known as prefix trees!)

For example, imagine you're building autocomplete functionality. If the user types in "pe", you want it to look like this:

With a trie you can traverse down from "p" to "e", and then that tree from "e" on down would be what you recommend to the user for the autocomplete: "pet", "pets" and "peck".

Now imagine that you had to implement autocomplete and had the words stored as an array instead of a trie.

[
  "pet",
  "pets",
  "peck",
  "pipe"
]

Well, your goal is to get all words that have "pe" as their prefix. So you'd have to go through each element in the array check if it has "pe" as it's prefix. Something like this:

const getWordsWithPrefix = (dictionary, prefix) => {
  return dictionary.filter(word => {
    if (word.startsWith(prefix)) {
      return true;
    } else {
      return false;
    }
  });
};

Or, more succinctly:

const getWordsWithPrefix = (dict, prefix) => dict.filter(w => w.startsWith(prefix));

The code is actually pretty clean and easy to write. The issue is with the time complexity: it's O(n). We have to check each word in the dictionary. Same thing if we used a hash as our data store. But when we use a trie, we don't have to screw around with stuff that's outside of the brown box in the image above. In this example it's not too big a deal, but when you have a big dictionary it does become a big deal.

There's more to the story of course, but that's what my my elevator pitch for tries would be.

Representation

There are actually different ways to represent a trie, and for each of these approaches there are different variants. Here I'll describe the approach that is simple and common. I think it makes sense to learn this approach first, and then later on you can learn the variants as a way to "level up" your understanding for "extra credit".

Basically, we want this in code:

The question is how we do that. Well, for starters, we're going to have nodes that are linked to each other. We're going to have a tree.

If you're like me, when you think of a tree data structure, your mind automatically goes to a binary tree, where the nodes have left and right pointers like this:

{
  val: null,
  left: null,
  right: null
}

But our tree isn't going to be a binary tree. It's actually going to be a 26-ary tree. Each node can have 26 children. One for each letter of the alphabet. (If you want to distinguish between upper and lower case letters, or if you want to include other characters, you'd need more than 26.)

I actually didn't make "26-ary" up! n-ary trees are a thing.

We could do something like this:

{
  val: null,
  aChild: null,
  bChild: null,
  cChild: null,
  ...
  zChild: null
}

Where we use stuff like aChild and bChild as pointers. But a more elegant approach is to have a children array with 26 slots. Index 0 corresponds to aChild, index 1 corresponds to bChild, etc.

{
  val: null,
  children: []
}

This is getting a little abstract. Let's see what our trie would actually look like for the dictionary of "pet", "pets" and "pipe. (We'll drop "peck" to keep the illustration simple.)

The one at the top is our root node. ∅ stands for "empty set" or "null". This root node has a pointer to our "p" node. The pointer would be stored in children[15] because "p" is the 16th letter of the alphabet and we start counting at zero.

Our "p" node has pointers to the "e" and "i" nodes.

Our "e" node has a pointer to the "t" node.

The "t" node is interesting. It's the first one that has a value. See val: "pet" in the illustration? The fact that it has a value represents the fact that "pet" is in our dictionary. On the other hand, the previous "e" node doesn't have a value, so "pe" is not in our dictionary.

There are other ways to represent what is and isn't in the dictionary though. And instead of storing the word, we could also store some sort of numeric value if we wanted to weight the word somehow. Like if we wanted to order the autocomplete based on how popular the choices are. Maybe "pet" has a weight of 10, "pets" has a weight of 8, and "peck" has a weight of 2. In that case we'd want to make sure our autocomplete is ordered: pet, pets, peck.

Search is actually pretty easy once we understand what our data structure looks like.

Imagine that we're searching for the word "pit". Here's how it works:

Basically, we're traversing from the root node on down, returning true if we "make it to the end", and returning false if we "can't continue".

There's one caveat though. Imagine that we search for "pip". Well, if we followed the logic above it would return true, but "pip" isn't in our dictionary, so it should be returning false. The catch is that once we "make it to the end", we have to check if that node has a val. That second "p" node doesn't have a val, so we'd return false even though we successfully "made it to the end".

On the other hand, imagine that we search for "pet". The "t" node for "pet" in fact does have a val, so we'd return true. It doesn't matter that it isn't a leaf node. What matters is that it has a val. When I say "make it to the end" it means the end of "pet", not making it to a leaf on the tree.

Here's what the code looks like:

class Trie {
  constructor() {
    this._root = {
      val: null,
      children: [],
    };
  }

  search(word) {
    let curr = this._root;
    let char;
    let charIndex;

    for (let i = 0; i < word.length; i++) {
      char = word[i];
      charIndex = char.charCodeAt() - 97;

      if (!curr.children[charIndex]) {
        return false;
      }

      curr = curr.children[charIndex];
    }

    return !!curr.val;
  }
}

Insertion

Insertion isn't too bad either. At a high level, we traverse through the tree like we did with search, and once we hit a node that doesn't have the child we need, we start inserting instead of traversing.

As an example, if we were inserting "pizza", we'd first traverse from "∅" to "p" to "i". Then when we're at "i" we can't traverse to "z", so we insert "z", "z", and "a".

Oh, almost forgot: when we hit the end, we have to make sure we set val.

Here's what the code looks like:

insert(word) {
  let curr = this._root;
  let char;
  let charIndex;

  for (let i = 0; i < word.length; i++) {
    char = word[i];
    charIndex = char.charCodeAt() - 97;

    if (!curr.children[charIndex]) {
      curr.children[charIndex] = {
        children: [],
        val: null,
      };
    }

    curr = curr.children[charIndex];
  }

  curr.val = word;
}

Starts with

Imagine that you want to see if any of the words in your dictionary start with "pe". Aka have the prefix of "pe". Hey! We're using a prefix tree (aka trie)! This should be easy!

I remember my first thought was to traverse from "∅" to "p" to "e" (returning false if we can't), and then do some sort of tree traversal with "e" as our root, looking for a node with a val. If we find one, we know that a word exists that starts with "pe", so we return true. If not, we return false.

That approach works. It's just unnecessary. Once you hit that "e" node, you can actually just stop there. The "e" node would have (usually!) gotten deleted if it wasn't a prefix.

Here's the code:

startsWith(prefix) {
  let curr = this._root;
  let char;
  let charIndex;

  for (let i = 0; i < prefix.length; i++) {
    char = prefix[i];
    charIndex = char.charCodeAt() - 97;

    if (!curr.children[charIndex]) {
      return false;
    }

    curr = curr.children[charIndex];
  }

  return !!curr;
}

On the other hand, maybe you want to return an array of words that have the prefix (eg. for autocomplete). Or even just the number of words that have the prefix. In those cases, you'd have to do the tree traversal once you hit "e" and collect/count everything that has a val from "e" on down.

Here's the code for returning the array of words:

getWordsWithPrefix(prefix) {
  let curr = this._root;
  let char;
  let charIndex;
  let wordsWithPrefix = [];

  // navigate to end of prefix
  for (let i = 0; i < prefix.length; i++) {
    char = prefix[i];
    charIndex = char.charCodeAt() - 97;

    if (curr.children[charIndex] === undefined) {
      return []; // no words with prefix
    }

    curr = curr.children[charIndex];
  }

  // collect words with prefix
  const traverseTree = (root) => {
    if (!root) {
      return;
    } else if (root.val) {
      wordsWithPrefix.push(root.val);
    }

    root.children.forEach(c => traverseTree(c));
  };
  traverseTree(curr);

  return wordsWithPrefix;
}

You could definitely extract a lot of this out into helper methods.

Deletion

There are two types of deletion: lazy and eager.

Imagine that you want to delete the word "pipe" from our dictionary of "pet", "pets" and "pipe". Let's reference our data structure again:

Well, "pipe" is represented by that last "e" node. If we set the val of that node to null and then tried to search for "pipe", you wouldn't find it. So doing this seems like it accomplishes the task of deleting "pipe" from our dictionary.

But then we'd be here:

The only difference is that val: null part. Now think about this: what if we called trie.startsWith("pi")? It'd return true, but that would be mistaken.

So we'd really prefer to delete those "i", "p" and "e" nodes as well. They're just dangling there, not serving any purpose. Doing so is called an eager deletion. Not doing so is known as a lazy deletion.

Note that it isn't strictly necessary to use eager deletion over lazy deletion. It's usually a good idea, but it does depend on the context. You might prefer to use lazy deletion and then perform the cleanup later on, like in the background or the next time someone calls another method like search.

Lazy deletion is pretty straightforward to implement: just navigate to the node and set node.val = null. But how would we implement eager deletion?

Well, first we do lazy deletion. We navigate to the node and set node.val = null. Then after that we have to do the cleanup. How do we do the cleanup?

Well, if node.children.length > 0, we don't have to do any cleanup. Like if we wanted to delete "pet", we wouldn't be removing the "t" node because it's needed for "pets".

But for "pipe", that "e" node doesn't have any children, so we do want to delete it.

Now think about the "p" node above the "e" node. Previously it had a child underneath it: the "e" node. But we just deleted that "e" node! So now the "p" node has no children, and we'd want to delete it as well.

Ok, let's continue this process. We just deleted the "p" and "e" nodes at the end of "pipe". What about the "i" node? Well, previously it has a child... but we just deleted that child... so now "i" is "dangling" as well, and we'd want to delete it.

Continuing... we just deleted "i", "p", and "e" in "pipe". Next up is "p". Should we delete "p"? Now the answer is finally "no"! Although this "p" node no longer points to "i", it still points to the "e" for "pet" and "pets", so we don't want to remove it. If we did, we'd be removing "pet" and "pets".

Once we hit this point, we're finished! We're not going to be deleting any nodes further up than this because if we did it'd delete this current "p" node, and we don't want to do that.

Ok, I think that makes enough sense conceptually. Now how do we implement it in code. It's a little bit tricky, and there are various approaches you can take. Here's one:

remove(word) {
  let curr = this._root;
  let char;
  let charIndex;
  let prevMap = new Map();
  let prev;

  // navigate to word
  for (let i = 0; i < word.length; i++) {
    char = word[i];
    charIndex = char.charCodeAt() - 97;

    if (!curr.children[charIndex]) {
      return false; // word doesn't exist
    }

    prevMap.set(curr.children[charIndex], curr);
    curr = curr.children[charIndex];
  }

  // set val to null
  curr.val = null;

  // remove nodes with no children
  while (curr.children.length === 0) {
    prev = prevMap.get(curr);
    prev.children[curr.val.charCodeAt() - 97] = null;
    curr = prev;
  }

  return true;
};

With this approach we keep track of previous nodes in prevMap (I'm using a map instead of an object because object's don't accept references as their keys). Everything else before // remove nodes with no children is just normal lazy deletion + building prevMap.

Then once we finished our lazy deletion and have our prevMap all set up we can traverse back upwards, deleting all of the nodes with no children. That's what the while loop is doing.

Finally, we're returning true if the deletion was successful, and false (in the // navigate to word block) if it failed.

You can also accomplish this recursively like so:

remove(word) { 
  this._root = this._delete(this._root, word, 0);
}

_remove(root, word, index) {
  if (!root) {
    return null;
  }

  if (index === word.length) {
    root.val = null;
  } else {
    let c = word.charCodeAt(index) - 97;

    root.children[c] = this._remove(root.children[c], word, index + 1);
  }

  if (root.val) {
    return root;
  }

  for (let i = 0; i < 26; i++) {
    if (root.children[i]) {
      return root;
    }
  }

  return null;
}

Word validation

You know how when you type in a text editor and make an error, you see the red squiggly lines underneath? Well, tries are a great tool for implementing that.

Imagine the following:

I'll let Gayle Laakmann McDowell elaborate:

IMAGE ALT TEXT HERE

Comparison to hash tables

When I was researching this post, I came across people comparing tries to hash tables. "Huh?", I thought to myself. "But tries look like this. And hashes look like that. Arrays and linked lists I could see, but not hashes and tries."

Then I started thinking about each of them as an interface. How they look from the outside. They're each black boxes that have get, set, has and remove methods. Don't think about how the methods are implemented or how the data is stored internally. Just think about the black box and what interface is presented to the outside. When you do that, they start to look pretty similar.

The big difference of course is that tries have prefix-related methods like startsWith and getWordsWithPrefix. But again, get, set, has and remove work similarly. So let's talk about tries vs. hashes from that perspective.

And let's start by talking about lookup. At first it felt to me like lookup is a good amount slower in tries. get, set, has and remove all involve lookups, so that felt like a big downside to tries. But let's think about it more carefully.

For tries, if you're looking up, say, "pet", you have to navigate from the root, to the "p" node, to the "e" node, to the "t" node. Let's say that there are m characters in the key "pet". So lookup is O(m). On the other hand, for hashes, lookup happens in constant time.

Or does it?????

I usually just wave my hands and chalk it up to constant time, but in fact, hashes take O(m) time for lookups too! Here's why. When we do a lookup in a hash table, we first run the key through our hashing function. The hashing function spits out an integer, and we use that integer to look it up in the array datastore. (Check out my video on hash tables for a refresher.) But that hashing function itself takes O(m) time to do it's thing. Think about it: it has to process each character in the key to figure out what output to produce, and there are m characters.

Ok, so the O(m) lookup really levels the playing field. What else is there to consider?

Well, hash collisions are a thing in hash tables, but we don't have to worry about them for tries, so that's good.

What about memory requirements? Well, for a hash we allocate memory for a nice big array as our underlying data store. For tries we allocate memory one node at a time. All things equal, it's nice to allocate memory in a big block, so that's good for hashes. On the other hand, we may end up allocating a block that is too big. We also may end up allocating a block that is too small, in which case we'd have to reallocate a bigger block and change our hash function if we run out of space. That's annoying.

What about locality? I'm not sure. One would think that since hashes have a nice contiguous array as their data store that they might do better with locality. But locality is one of those things that really ends up depending on optimizations and implementation details and low level stuff that only the truly hardcore people know about. I'm just a mere mortal over here, so I don't really know.

And I think this discussion is getting us a little sidetracked anyway. This is meant to be an overview article, so these details aren't actually important right now. The big thing to take away is that tries are in fact comparable to hashes.

If you have any thoughts, I'd love to discuss them over email: adamzerner@protonmail.com.

If you'd like to subscribe, you can do so via email or RSS feed.

#code