Trie

Explanation

In a trie, the root represents an empty string. Each edge from a parent to a child represents a character. Following edges from the root spells out a word. A node marked as a word-end (isEnd = true) indicates a complete word exists at that prefix. This structure means every operation — insert, search, startsWith — takes O(m) time where m is the word length, regardless of how many words are stored. The classic trie node has an array of 26 children (one per lowercase English letter) or a hash map for arbitrary character sets. The hash map approach uses less memory when the character set is large or words are sparse. Each TrieNode also stores a boolean (isEndOfWord) to distinguish "the" as a complete word vs. the prefix "the" as the start of "there" and "their." Tries shine at two use cases: autocomplete/search-as-you-type (given a prefix, find all words that start with it — trie supports this in O(prefix length + results) time) and spell checking (test whether a word exists in a dictionary in O(m) time). They can also compress into a compressed trie (PATRICIA trie/radix tree) where chains of single-child nodes are merged, reducing memory usage significantly. The main downside of tries is memory: each node can have up to 26 children (or a whole HashMap), and deep tries can consume significant RAM for large dictionaries. For this reason, compressed tries or hash-based dictionaries are preferred in memory-constrained production environments.

Code Example

// Trie with insert, search, and startsWith
class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

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

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) 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 t = new Trie();
['apple', 'app', 'apply'].forEach(w => t.insert(w));
console.log(t.search('app'));       // true
console.log(t.startsWith('appl'));  // true
console.log(t.search('application')); // false

Why It Matters for Engineers

Tries power the autocomplete in every search box you've ever typed into. Understanding how they work helps you design fast, scalable search features. When you see a search-as-you-type requirement, reaching for a trie (or a production implementation like Elasticsearch's prefix queries) is the correct engineering decision. The trie also illustrates an important design principle: tailor your data structure to your access pattern. A hash map is O(1) for exact key lookup but can't efficiently support prefix queries. A trie is O(m) for all operations but also supports prefix queries at no extra cost. Knowing when to use which structure separates engineers who understand their tools from those who reach for whatever's familiar.