How to Implement Trie in JavaScript: Simple Guide and Example

To implement a Trie in JavaScript, create a class with nodes that store children in a map and a flag for word endings. Use methods to insert words by adding nodes for each letter and to search by traversing nodes letter by letter.

Syntax

A Trie is built using a TrieNode class to represent each letter node, and a Trie class to manage insertion and search.

• TrieNode: Holds children nodes and a boolean to mark word end.
• Trie: Has a root node and methods like insert(word) and search(word).

javascript

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

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char);
    }
    return node.isEndOfWord;
  }
}

Example

This example shows how to create a trie, insert words, and search for them. It demonstrates that the trie can find exact words and reject words not inserted.

javascript

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

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char);
    }
    return node.isEndOfWord;
  }
}

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('dog');

console.log(trie.search('cat'));
console.log(trie.search('car'));
console.log(trie.search('dog'));
console.log(trie.search('cow'));

Output

true
true
true
false

Common Pitfalls

Common mistakes when implementing a trie include:

• Not marking the end of a word, causing search to give false positives.
• Using plain objects instead of Map, which can cause key collisions with prototype properties.
• Failing to handle empty strings or non-string inputs.

javascript

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

// Wrong: Using plain object for children can cause bugs
// Right: Use Map for children to avoid key conflicts

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

  insert(word) {
    if (typeof word !== 'string' || word.length === 0) return;
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEndOfWord = true;
  }

  search(word) {
    if (typeof word !== 'string' || word.length === 0) return false;
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char);
    }
    return node.isEndOfWord;
  }
}

Quick Reference

• TrieNode: Stores children as Map and isEndOfWord flag.
• insert(word): Adds each character node, marks end.
• search(word): Checks nodes for each character, returns true if end marked.
• Use Map for children to avoid key conflicts.
• Always mark isEndOfWord to distinguish words.

Key Takeaways

Use a TrieNode class with a Map for children and a boolean to mark word ends.

Insert words by creating nodes for each letter and marking the last node as end of word.

Search by traversing nodes for each letter and checking the end-of-word flag.

Avoid using plain objects for children to prevent key conflicts; prefer Map.

Always handle edge cases like empty strings and non-string inputs.