jsschools

Trie (Prefix Tree)

A tree where each path from root to a node spells a prefix, enabling O(m) search and insert for strings of length m.

Spec ↗

Syntax

class TrieNode { constructor() { this.children = {}; this.isEnd = false; } }
class Trie { insert(word) {...} search(word) {...} startsWith(prefix) {...} }

Parameters

NameTypeRequiredDescription
word string Yes The string to insert into or search within the trie.

Returns

Trie — A new Trie instance.

Examples

class TrieNode {
  constructor() { this.children = {}; this.isEnd = false; }
}
class Trie {
  #root = new TrieNode();
  insert(word) {
    let node = this.#root;
    for (const ch of word) {
      node.children[ch] ??= new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }
  search(word) {
    let node = this.#root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return node.isEnd;
  }
  startsWith(prefix) {
    let node = this.#root;
    for (const ch of prefix) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return true;
  }
}
const trie = new Trie();
['apple', 'app', 'application', 'apt'].forEach(w => trie.insert(w));
console.log(trie.search('app'));
console.log(trie.search('ap'));
console.log(trie.startsWith('ap'));
Output 
true
false
true

// Auto-complete: collect all words with a given prefix
function autocomplete(trie, prefix) {
  // navigate to prefix node then DFS collect words
  const results = [];
  // (abbreviated — walk children recursively appending characters)
  return results;
}
console.log('Tries power autocomplete in O(prefix_len + matches)');
Output 
Tries power autocomplete in O(prefix_len + matches)

Notes

| Operation | Time | Space | |-----------|------|-----------------| | Insert | O(m) | O(m * alphabet) | | Search | O(m) | O(1) | | StartsWith| O(m) | O(1) | | Delete | O(m) | O(1) | m = length of the word. Space is O(n * m * alphabet_size) in the worst case (n words, no shared prefixes). A compressed trie (Patricia/Radix tree) reduces space by merging single-child nodes. Use a Map instead of an object for the children to handle Unicode.

See also