Learning Tries in Javascript

In this weeks article I'm going to be discussing Tries. A Trie is a data structure thats main purpose is retrieval. Tries are most often used to store and retrieve strings in O(L) time, where L is the length of the string. A common use of a Trie data structure is to do prefix searching, such as an autocomplete form.

As you can see in the example above, each node contains a letter. Each chain of nodes will result in a string. In theory we could use a trie to store every word in the dictionary, but that would use an incredible amount of memory. For this reason Tries are often replaced by other data structures when a prefix search isn't necessary.

Tries have two main functions:

• Insert
• Search

But before we dive into those, let's first start with implementing the overall structure.

We need to create two classes, a node class and our tree class. Each node will contain a value, which is the letter it represents, a boolean representing if it's the last letter in a word, and an object for holding the nodes children. The Trie will only need the root, which is initialized as an empty node.

For our insert method we need to traverse through our tree. So to start we initialize a node variable representing the node we are currently on, and set it to the root. For each character in the passed in word, we see if our current node is holding the character as a child, if it isn't we add it as a child. We then change our current node to that character and repeat until we've gone through the word. After our traversal we set the last node's status to show it is the last character of a word.

Our search method is similar to our insert method in that we are doing another traversal. However, all we do in the loop is check if each letter is present in the word. If all of the characters are there and the last character's status shows it's the last character of a word then we return true, otherwise we return false.

Thanks for reading! You can find the code for this post here.

Comments

[Jon Randy 🎖️]

This code is very confused. You define a Node class and only use it once. Further code reverts to using plain objects. You might want to revise this example to either use the Node class throughout (and its data, children properties etc.), or just use plain objects throughout (remove the Node class, and make root {}).

You've also stated that:

A Trie is a data structure thats main purpose is retrieval

But you haven't shown an example of how that can be done! (Hint: the original Node class might be useful for this, if fully integrated)

Other issues:

• The search function returns null or true instead of true/false as stated
• The node !== null part of the return expression is entirely redundant, since it is always true
• Even if you remove the redundant first term of the expression, the remainder still has redundancy. You could simply just return node.isEndOfWord (although this would still be returning null/true - but this isn't a big issue as JS has the concept of truthiness and falsiness)

[Jon Randy 🎖️]

UPDATE: On further inspection, it's more luck than judgement that the search method even works - especially where you are checking for === null - you won't find a null anywhere. Overall, your code will be finding a lot of undefineds everywhere