Ex. Implementing a Trie

To re-iterate, Trie (pronounced "try") is a tree-like data structure that stores a dynamic set of strings, typically used to facilitate operations like searching, insertion, and deletion. Tries are particularly useful for tasks that require quick lookups of strings with a common prefix, such as in text autocomplete or in a Router implementation to find the matching paths.

Here's an illustration that shows how does a Trie look like in theory:

Here's how you can visualize the Trie above based on the words "OK", "TO", "CAR", "CAT", and "CUP":

Root Node

The Trie starts with a root node that doesn't hold any character. It serves as the starting point of the Trie.

      Root
     /  |  \
    T   O   C

• Level 1: You have the characters "O", "T", and "C" branching from the root node.
• Level 2 and Beyond: These nodes further branch out to form the words.
  • "O" branches to "K", completing the word "OK".
  • "T" branches to "O", completing the word "TO".
  • "C" branches to "A" and "U":
    • "A" further branches to "R" for "CAR" and "T" for "CAT".
    • "U" further branches to "P", completing the word "CUP".

End of the word

The "end of the word" is often represented by a boolean flag at a node to signify that the path from the root of the Trie to that node corresponds to a complete word. This flag helps distinguish between a string that is merely a prefix and one that is a full word in the Trie.

For example, consider a Trie that stores the words "car", "cat", and "cup". The node corresponding to the last 't' in "cat" and the last 'p' in "cup" would have the end-of-word marker, indicating that they are complete words, as opposed to just prefixes. Same for 'k' in "ok" and 'o' in "to"

By doing so, if someone searches for "ca" it should not return true, since we only stored "cat" and "car" where as "ca" is just a prefix.

Here's an another illustration to explain the "end-of-word" (EOW):

Challenge 1: Basic Trie with insert Method

In this first challenge, your task is to implement a Trie data structure with only one functionality: inserting a word into the Trie.

Requirements

1. Create a class called Trie.
2. Implement an insert(word) method that takes a string word and inserts it into the Trie.

More details

1. Initialization: You'll begin with a root node. This node will be the starting point for all word insertions, and it won't store any character itself.

2. Traversal: For each character in the word you want to insert, you'll traverse the Trie from the root node, going as far down as the current character sequence allows.

3. Node Creation: If a character in the word doesn't match any child node of the current node:

   • Create a new node for that character.
   • Link this new node to the current one.
   • Move down to this new node and continue with the next character in the word.

4. End-of-Word: When you've inserted all the characters for a particular word, mark the last node in some way to indicate that it's the end of a valid word. This could be a boolean property in the node object, for example.

Here's the boilerplate to get you started.

class TrieNode {
  constructor() {
    this.children = new Map(); // To store TrieNode children with char keys
    // this.children = new Map(); You may also use a Map instead.
    this.isEndOfWord = false; // To mark the end of a word
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    // Your code here
  }
}

Once implemented, your code should allow operations like:

const trie = new Trie();
trie.insert("hello");

Go ahead and implement the insert method, and then share your code to help others or to receive feedback in the Github discussions section. I'll try to review all the code submissions and provide feedback if required.

Great. You just implemented a Trie which is a Tree data structure. You've also wrote code to traverse a tree which is generally called "tree traversal".

Solution

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(wordToInsert, node = this.root) {
    let length = wordToInsert.length;
    if (length == 0) return;

    const letters = wordToInsert.split("");

    const foundNode = node.children.get(wordToInsert[0]);

    if (foundNode) {
      this.insert(letters.slice(1).join(""), foundNode);
    } else {
      let insertedNode = node.add(letters[0], length == 1);
      this.insert(letters.slice(1).join(""), insertedNode);
    }
  }
}

class TrieNode {
  constructor() {
    /**
     * Children will be Map<key(String), node(TrieNode)>
     */
    this.isEndOfWord = false;
    this.children = new Map();
  }

  add(letter, _isLastCharacter) {
    let newNode = new TrieNode();
    this.children.set(letter, newNode);

    if (_isLastCharacter) newNode.isEndOfWord = true;
    return newNode;
  }
}

const trie = new Trie();
trie.insert("node");
trie.insert("note");
trie.insert("not");

Let's take a look at the code:

class TrieNode {
  constructor() {
    this.isEndOfWord = false;
    this.children = new Map();
  }
}

Initializes an instance of the TrieNode class. A TrieNode has two properties:

• isEndOfWord: A boolean flag that denotes whether the node is the last character of a word in the Trie. Initially set to false.
• children: A Map to store the children nodes. The keys are letters, and the values are TrieNode objects.

add(letter, _isLastCharacter) {
        let newNode = new TrieNode();
        this.children.set(letter, newNode);

        if (_isLastCharacter) newNode.isEndOfWord = true;
        return newNode;
}

I've created a utility method on TrieNode to extract some logic from the Trie.insert method. This adds a new TrieNode as a child of the current node, corresponding to the given letter.

class Trie {
  insert(wordToInsert, node = this.root) {
    let length = wordToInsert.length;

    // Exit condition: If the word to insert is empty, terminate the recursion.
    if (length == 0) return;

    // Convert the string into an array of its individual characters.
    const letters = wordToInsert.split("");

    // Attempt to retrieve the TrieNode corresponding to the first letter
    // of the word from the children of the current node.
    const foundNode = node.children.get(wordToInsert[0]);

    if (foundNode) {
      // The first letter already exists as a child of the current node.
      // Continue inserting the remaining substring (sans the first letter)
      // starting from this found node.
      this.insert(letters.slice(1).join(""), foundNode);
    } else {
      // The first letter doesn't exist in the children of the current node.
      // Create a new TrieNode for this letter and insert it as a child of the current node.
      // Also, set the node's 'isEndOfWord' flag if this is the last character of the word.
      let insertedNode = node.add(letters[0], length == 1);

      // Continue inserting the remaining substring (without the first letter)
      // starting from this new node.
      this.insert(letters.slice(1).join(""), insertedNode);
    }
  }
}

The previous code looks fine. However, as our backend library/framework prioritizes performance, we will optimize the code we write in the upcoming exercises to improve efficiency.

The code above is acceptable, and not a bad implementation. But we can do better.

Using a for loop instead of recursion

I am not a big fan of recursion, and I prefer using loops over recursion most of the time. For loop is much easier to reason about and as someone who's reading the code, it's easier to understand what's going on.

Let's update our submission to use a for loop instead of recursion.

/** this class remains identical **/
class TrieNode {
  isEndOfWord = false;
  children = new Map();
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word, node = this.root) {
    const wordLength = word.length;
    if (wordLength === 0) return;

    for (let idx = 0; idx < wordLength; idx++) {
      let char = word[idx];

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

      // Move to the child node corresponding to the current character.
      node = node.children.get(char);
    }

    node.isEndOfWord = true;
  }
}

Challenge 2: Implement search method

Now that we have a Trie with insertion capabilities, let's add a search method.

Requirements

1. Add a search(word) method to the Trie class.
2. The method should return true if the word exists in the Trie and false otherwise.

More details

1. Start at the Root: Begin your search at the root node.
2. Traversal: For each character in the word, traverse down the Trie, going from one node to its child that corresponds to the next character.
3. Word Existence: If you reach a node that is marked as the end of a word (isEndOfWord = true), and you've exhausted all the characters in the word you're searching for, then the word exists in the Trie.

Once implemented, your code should allow:

const trie = new Trie();
trie.insert("code");
trie.insert("coding");

let found = trie.search("code");
console.log(found); // true

found = trie.search("cod");
console.log(found); // false

Go ahead and implement the Trie.search method. Don't read anything below before implementing it yourself.

If you are having trouble or are stuck, here are some hints to help you with the implementation -

Hints

1. Starting Point: Similar to the insert method, you'll start at the root node and traverse the Trie based on the characters in the word you're searching for.

2. Character Check: For each character in the word, check if there's a child node for that character from the current node you're at.

   • If Yes: Move to that child node.
   • If No: Return false, as the word can't possibly exist in the Trie.

3. End-of-Word Check: If you've reached the last character of the word, check the isEndOfWord property of the current node. If it's true, the word exists in the Trie; otherwise, it doesn't.

4. Recursion or Loop: You can choose to implement this method either recursively or iteratively.

   • Recursion: If you opt for recursion, you might want to include an additional parameter in the search method for the current node, similar to how you did it for the insert method.
   • Loop: If you prefer loops, you can use a for loop to go through each character in the word, updating your current node as you go along.

5. Return Value: Don't forget to return true or false to indicate whether the word exists in the Trie.

Good luck!

Solution

Again, I chose to implement tree traversal using a for loop instead of recursion.

search(word) {
    // Initialize 'currentNode' to the root node of the Trie.
    let currentNode = this.root;

    // Loop through each character in the input word.
    for (let index = 0; index < word.length; index++) {

        // Check if the current character exists as a child node
        // of the 'currentNode'.
        if (currentNode.children.has(word[index])) {

            // If it does, update 'currentNode' to this child node.
            currentNode = currentNode.children.get(word[index]);
        } else {

            // If it doesn't, the word is not in the Trie. Return false.
            return false;
        }
    }

    // After looping through all the characters, check if the 'currentNode'
    // marks the end of a word in the Trie.
    return currentNode.isEndOfWord;
}

Awesome work. Now you know the basics of the Trie data structure and how to implement it. In the next exercise, we'll implement our Router from scratch! The next exercise will be more challenging and exhaustive.