Tries (Prefix Trees)

Node Implementation

A typical trie node class or structure in JavaScript:

class TrieNode {
  constructor() {
    // Children map with character as key and TrieNode as value
    this.children = new Map();
    
    // Flag to indicate if this node represents the end of a word
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    // Root of the trie
    this.root = new TrieNode();
  }
  
  // Other methods will be added here
}

Some implementations may use a fixed-size array for the children (e.g., size 26 for lowercase English letters), while others use a hash map or object for flexibility and to handle larger character sets.

4. Deletion

Deletion from a trie is more complex than the other operations. We need to:

• Find the node representing the last character of the word
• Mark it as not the end of a word (if needed)
• Remove nodes that are not used by any other word (to save space)

Deletion is typically implemented recursively, working from the end of the word back to the root.

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

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

  // Insert a word into the trie
  insert(word) {
    let current = this.root;
    
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      
      current = current.children.get(char);
    }
    
    current.isEndOfWord = true;
  }

  // Search for a word in the trie
  search(word) {
    let current = this.root;
    
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      
      if (!current.children.has(char)) {
        return false;
      }
      
      current = current.children.get(char);
    }
    
    return current.isEndOfWord;
  }

  // Check if there is any word in the trie that starts with the given prefix
  startsWith(prefix) {
    let current = this.root;
    
    for (let i = 0; i < prefix.length; i++) {
      const char = prefix[i];
      
      if (!current.children.has(char)) {
        return false;
      }
      
      current = current.children.get(char);
    }
    
    return true;
  }

  // Delete a word from the trie
  delete(word) {
    this._deleteRecursive(this.root, word, 0);
  }

  // Helper method for delete
  _deleteRecursive(current, word, index) {
    // Base case: end of word reached
    if (index === word.length) {
      // Word exists in trie, so unmark the end of word
      if (current.isEndOfWord) {
        current.isEndOfWord = false;
      }
      
      // Return true if node has no children (can be deleted)
      return current.children.size === 0;
    }

    const char = word[index];
    const node = current.children.get(char);
    
    // Word not found in trie
    if (!node) {
      return false;
    }

    // Recursively delete for next character
    const shouldDeleteNode = this._deleteRecursive(node, word, index + 1);

    // If child node can be deleted, remove it from the map
    if (shouldDeleteNode) {
      current.children.delete(char);
      
      // Current node can be deleted if it's not the end of another word
      // and has no other children
      return !current.isEndOfWord && current.children.size === 0;
    }

    return false;
  }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("application");

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

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

Space Complexity

The space complexity of a trie is more complex to analyze:

• Worst case: O(n × m), where n is the number of keys and m is the length of the longest key
• Best case: O(n) when all keys share most of their prefixes
• Each node may need to store references to up to 26 children (for English alphabet) or more for larger character sets

While tries can be memory-intensive, they offer trade-offs with speed that make them valuable for many applications.