Tries

What is a Trie?

A Trie (prefix tree) is a tree-like data structure for storing strings. Each node represents a character, making it perfect for autocomplete, spell checkers, and prefix searches.

Trie Implementation

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;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true;
  }

  autocomplete(prefix) {
    let node = this.root;

  

    
Learn More
    

      
        
GeeksforGeeks: Trie
        
Learn how to implement and use Trie data structures.
      
      
        
LeetCode: Trie
        
Solve advanced string problems using Tries.
      
    
  

    // Navigate to prefix
    for (const char of prefix) {
      if (!node.children[char]) return [];
      node = node.children[char];
    }
    
    // Collect all words with this prefix
    const results = [];
    this.collectWords(node, prefix, results);
    return results;
  }

  collectWords(node, currentWord, results) {
    if (node.isEndOfWord) {
      results.push(currentWord);
    }
    for (const char in node.children) {
      this.collectWords(node.children[char], currentWord + char, results);
    }
  }
}

// Usage
const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("application");
console.log(trie.search("app"));           // true
console.log(trie.startsWith("app"));       // true
console.log(trie.autocomplete("app"));     // ['app', 'apple', 'application']