Trie (Prefix Tree)

A trie (pronounced "try") is a tree-shaped data structure purpose-built for storing and searching strings. Unlike a hash map where every key is treated as a black box, a trie exploits the shared prefix structure of strings — every node represents a single character and all descendants share the path from root to that node as a common prefix.

Note

The name comes from re**trie**val. Tries are the backbone of autocomplete engines, spell checkers, IP routing tables, and DNA sequence databases.

Visual Structure

Inserting the words "apple", "app", "ape", and "bat" builds this trie:

Text

root
├── a
│   └── p
│       ├── p (*)           ← "app" ends here
│       │   └── l
│       │       └── e (*)   ← "apple" ends here
│       └── e (*)           ← "ape" ends here
└── b
    └── a
        └── t (*)           ← "bat" ends here

(*) = isEndOfWord flag is true

Every node stores:

A map from character → child node
A boolean isEndOfWord marking complete words

TrieNode & Trie Class

class TrieNode {
  constructor() {
    this.children = {};   // char → TrieNode
    this.isEnd   = false;
    this.count   = 0;     // words passing through this node (useful for prefix counts)
  }
}

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

  // ── INSERT ─────────────────────────────────────────── O(L)
  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.count++;          // increment prefix counter
    }
    node.isEnd = true;
  }

  // ── SEARCH (exact word) ────────────────────────────── O(L)
  search(word) {
    const node = this._walk(word);
    return node !== null && node.isEnd;
  }

  // ── STARTS-WITH (prefix check) ────────────────────── O(L)
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }

  // ── COUNT words with given prefix ─────────────────── O(L)
  countPrefix(prefix) {
    const node = this._walk(prefix);
    return node ? node.count : 0;
  }

  // internal: walk to the end of a string, return null if path missing
  _walk(s) {
    let node = this.root;
    for (const ch of s) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }
}

Complexity at a Glance

Operation	Time	Space	Notes
insert(word)	O(L)	O(L)	L = word length; worst case new nodes per char
search(word)	O(L)	O(1)	Traversal only, no allocation
startsWith(prefix)	O(L)	O(1)	Same traversal, skip isEnd check
countPrefix(prefix)	O(L)	O(1)	Requires count field on nodes
Space (all n words)	—	O(n · L)	Shared prefixes reduce real usage

Note

Compared to a hash map, a trie uses more memory per key but enables O(L) prefix queries that a hash map cannot answer without iterating all keys.

Autocomplete

Given a prefix, return all words stored in the trie that begin with it. Walk to the prefix node, then DFS/BFS to collect every path that ends at an isEnd node.

// Returns all words in the trie that start with 'prefix'
Trie.prototype.autocomplete = function(prefix) {
  const results = [];
  const node = this._walk(prefix);
  if (!node) return results;

  // DFS from the prefix node
  const dfs = (cur, path) => {
    if (cur.isEnd) results.push(path);
    for (const [ch, child] of Object.entries(cur.children)) {
      dfs(child, path + ch);
    }
  };

  dfs(node, prefix);
  return results;
};

// ── Demo ──────────────────────────────────────────────
const trie = new Trie();
['apple', 'app', 'application', 'apply', 'ape', 'bat'].forEach(w => trie.insert(w));

console.log(trie.autocomplete('app'));
// → ['app', 'apple', 'application', 'apply']

['app', 'apple', 'application', 'apply']

Longest Common Prefix

Find the longest string that is a prefix of every word in an array. Walk the trie from the root while each node has exactly one child and is not itself a word-end.

function longestCommonPrefix(words) {
  const trie = new Trie();
  words.forEach(w => trie.insert(w));

  let prefix = '';
  let node = trie.root;

  while (true) {
    const keys = Object.keys(node.children);
    // branch point OR a complete word → stop
    if (keys.length !== 1 || node.isEnd) break;
    const ch = keys[0];
    prefix += ch;
    node = node.children[ch];
  }
  return prefix;
}

console.log(longestCommonPrefix(['flower', 'flow', 'flight'])); // 'fl'
console.log(longestCommonPrefix(['dog', 'racecar', 'car']));    // ''

'fl'
''

Word Dictionary with Wildcards (LeetCode 211)

Design a data structure that supports addWord(word) and search(pattern) where a pattern may contain '.' matching any single character. A dot forces us to branch into all children at that level — use recursion.

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

  addWord(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(pattern) {
    return this._dfs(this.root, pattern, 0);
  }

  _dfs(node, pattern, i) {
    if (i === pattern.length) return node.isEnd;
    const ch = pattern[i];

    if (ch === '.') {
      // try every possible child
      for (const child of Object.values(node.children)) {
        if (this._dfs(child, pattern, i + 1)) return true;
      }
      return false;
    }

    if (!node.children[ch]) return false;
    return this._dfs(node.children[ch], pattern, i + 1);
  }
}

// ── Demo ──────────────────────────────────────────────
const dict = new WordDictionary();
['bad', 'dad', 'mad'].forEach(w => dict.addWord(w));

console.log(dict.search('pad'));  // false
console.log(dict.search('bad'));  // true
console.log(dict.search('.ad'));  // true  (b/d/m + ad)
console.log(dict.search('b..'));  // true

false
true
true
true

Word Search II (Find all words on a board)

Given an m × n board of characters and a list of words, return every word that can be formed by adjacent (no-reuse) cells. The trick: build a trie of all words, then DFS the board — prune entire branches when the current path doesn't match any trie prefix.

function findWords(board, words) {
  // Build trie
  const trie = new Trie();
  words.forEach(w => trie.insert(w));

  const rows = board.length, cols = board[0].length;
  const found = new Set();

  const dfs = (node, r, c, path) => {
    const ch = board[r][c];
    if (!node.children[ch]) return;   // prune: no matching prefix

    const next = node.children[ch];
    const word = path + ch;
    if (next.isEnd) found.add(word);

    board[r][c] = '#';  // mark visited
    for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
        dfs(next, nr, nc, word);
      }
    }
    board[r][c] = ch;   // restore
  };

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      dfs(trie.root, r, c, '');
    }
  }
  return [...found];
}

const board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v'],
];
console.log(findWords(board, ['oath','pea','eat','rain']));

['oath', 'eat']

Tip

Add a "prune dead branches" step after marking a word found: delete the child reference when a subtree has no more words left. This can cut DFS time dramatically on large word lists.

Count Words With a Given Prefix

Store a count field on every node incremented during insert. Then countPrefix(prefix) is a single O(L) walk — no DFS needed.

// Using the Trie class with count field from earlier
const t = new Trie();
['apple', 'app', 'application', 'apply', 'ape', 'bat'].forEach(w => t.insert(w));

console.log(t.countPrefix('app'));  // 4  (app, apple, application, apply)
console.log(t.countPrefix('ap'));   // 5  (+ ape)
console.log(t.countPrefix('ba'));   // 1  (bat)
console.log(t.countPrefix('xyz')); // 0

Delete a Word

Deleting requires a post-order recursive walk: unmark isEnd, then on the way back up remove any child node that is now a leaf with no words beneath it.

Trie.prototype.delete = function(word) {
  const _del = (node, word, depth) => {
    if (!node) return false;

    if (depth === word.length) {
      if (!node.isEnd) return false;  // word didn't exist
      node.isEnd = false;
      node.count--;
      return Object.keys(node.children).length === 0; // leaf? caller may remove
    }

    const ch = word[depth];
    if (!node.children[ch]) return false;

    node.count--;
    const shouldDelete = _del(node.children[ch], word, depth + 1);
    if (shouldDelete) delete node.children[ch];
    return !node.isEnd && Object.keys(node.children).length === 0;
  };

  _del(this.root, word, 0);
};

Interview Cheat Sheet

Problem pattern	Approach
Autocomplete / type-ahead	Insert all words; walk to prefix; DFS collect
Prefix existence check	startsWith in O(L)
Word count by prefix	count field on nodes
Wildcard search (. or *)	Recursive DFS branching at wildcard nodes
Word search on 2-D grid	Trie + board DFS; prune on missing prefix
Longest common prefix	Walk while single-child and not isEnd
XOR maximization	Bit-trie: store binary; greedily take opposite bit

Warning

A trie over 26-char alphabet can use up to 26× more pointers than a hash map for the same key set. Use a Map instead of a plain object for children when the character set is large (e.g. Unicode), or use a compressed trie (Patricia/radix tree) when many nodes have only one child.

Key Takeaways

A trie stores strings character-by-character; all words sharing a prefix share a path from the root.
Insert, search, and startsWith all run in O(L) time — independent of how many words are stored.
The isEnd flag distinguishes a full word from a mere prefix of another word.
A count field on each node enables O(L) prefix-frequency queries without any DFS.
For wildcard patterns, branch into all children at a dot; use recursion to backtrack.
For board word-search problems, build a trie first so you can prune the DFS early.
Delete requires a post-order pass to garbage-collect now-empty leaf nodes.