Q37: Implement Trie (Prefix Tree)

Implement a Trie with insert, search, and startsWith methods for efficient string retrieval.

Trie Prefix Tree Implementation

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

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

  insert(word) {
    let node = this.root;
    for (let 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 (let char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

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

const trie = new Trie();
trie.insert('apple');
console.log(trie.search('apple'));   // true
console.log(trie.startsWith('app')); // true

💡 Nodes contain a child map and end-of-word boolean. Character insertions create tree branches; searches follow character edges step by step.

Key Takeaways

Tree data structure where nodes represent individual character character branches.
Enables $O(m)$ string insertions and prefix lookups where $m$ is string length.

Knowledge Check

What differentiates search(word) from startsWith(prefix) in a Trie?

Q37: Implement Trie (Prefix Tree)

STAY UPDATED WITH BYTES!