Trie

A trie is a tree-like data structure used to store a dynamic set of strings where each node represents a common prefix of its descendants.

A trie is a special tree that can compactly store strings.

Here's a trie that stores ‘this’, ‘there’, ‘that’, ‘does’, ‘did’.

Data Structures and Algorithms Cheatsheet - 26

Notice that we only store "there" once, even though it appears in two strings: "that" and "this".

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

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

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

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

  remove(word) {
    let node = this.root;
    this._removeHelper(node, word, 0);
  }

  _removeHelper(node, word, index) {
    if (index === word.length) {
      if (!node.isEndOfWord) {
        return false;
      }
      node.isEndOfWord = false;
      return Object.keys(node.children).length === 0;
    }

    const char = word[index];
    if (!node.children[char]) {
      return false;
    }

    const shouldDeleteCurrentNode = this._removeHelper(node.children[char], word, index + 1);

    if (shouldDeleteCurrentNode) {
      delete node.children[char];
      return Object.keys(node.children).length === 0;
    }

    return false;
  }

  rotate(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        return false; // Word not found
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
    return true;
  }

  reverse(word) {
    let node = this.root;
    for (let i = word.length - 1; i >= 0; i--) {
      const char = word[i];
      if (!node.children[char]) {
        return false; // Word not found
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
    return true;
  }

  insertAt(word, index) {
    let node = this.root;
    for (let i = 0; i < index; i++) {
      const char = word[i];
      if (!node.children[char]) {
        return false; // Word not found
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
    return true;
  }

  removeAt(word, index) {
    let node = this.root;
    for (let i = 0; i < index; i++) {
      const char = word[i];
      if (!node.children[char]) {
        return false; // Word not found
      }
      node = node.children[char];
    }
    if (!node.children[word[index]]) {
      return false; // Word not found
    }
    delete node.children[word[index]];
    return true;
  }

  printList(prefix = '', node = this.root) {
    if (node.isEndOfWord) {
      console.log(prefix);
    }
    for (const char in node.children) {
      this.printList(prefix + char, node.children[char]);
    }
  }
}

// Example usage:
const trie = new Trie();
trie.insert("apple");
trie.insert("banana");
trie.insert("orange");

console.log("Search 'apple':", trie.search("apple")); // Output: true
console.log("Search 'grape':", trie.search("grape")); // Output: false

trie.remove("banana");
console.log("Search 'banana' after removal:", trie.search("banana")); // Output: false

trie.rotate("orange");
console.log("Search 'orange' after rotation:", trie.search("orange")); // Output: true

console.log("Words in the trie:");
trie.printList();

Trie Strengths 😀:

• Sometimes Space-Efficient.

• If you're storing lots of words that start with similar patterns, tries may reduce the overall storage cost by storing shared prefixes once.

• Efficient Prefix Queries. Tries can quickly answer queries about words with shared prefixes, like:

  • How many words start with "choco"?

  • What's the most likely next letter in a word that starts with "strawber"?

Trie Weaknesses 😒:

• Usually Space-Inefficient. Tries rarely save space when compared to storing strings in a set.

  • ASCII characters in a string are one byte each.

  • Each link between trie nodes is a pointer to an address—eight bytes on a 64-bit system.

  • So, the overhead of linking nodes together often outweighs the savings from storing fewer characters.

• Not Standard. Most languages don't come with a built-in trie implementation.

• You'll need to implement one yourself.

Tries Time Complexity: O (length of the word)