Trie

In this chapter you will learn the basics of Trie data structure and how to apply it in a different problems.

A trie is a tree-like data structure that is used to store a dynamic set of strings. Tries are commonly used to store the entire English language dictionary for quick lookups, autocomplete, spell-checking and IP routing tables.

Structure of a Trie

• Nodes. Each node in a Trie represents a character of a string. The root node is typically empty, representing the start of any string.
• Edges. The edges between nodes represent the connection between characters in the sequence.
• End Markers. Some implementations mark the end of a string with a special indicator (like a boolean flag) to distinguish between words that have a common prefix

Basic Operations

• Insertion. The process of inserting a word into a trie involves traversing the trie from the root, creating new nodes for characters that don't exist, and marking the last node as the end of a word.
• Search. Searching for a word in a trie involves traversing the trie from the root, following the path corresponding to the characters in the word.
• Prefix Search

Problem

Given a list of words, write a function to implement a trie data structure.

Example of usage:

let trie = new Trie();

trie.insert("apple");
console.log(trie.search("apple")); // true
console.log(trie.search("app")); // false
console.log(trie.startsWith("app")); // true

trie.insert("app");
console.log(trie.search("app")); // true

Solution

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

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

  insert(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      let char = word[i];
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      let char = word[i];
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

  startsWith(prefix) {
    let node = this.root;
    for (let i = 0; i < prefix.length; i++) {
      let char = prefix[i];
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }
}

Complexity Analysis

• The time complexity of the insert, search, and startsWith methods is O(m) where m is the length of the word or prefix.
• The space complexity is O(n) where n is the total number of characters in the trie.