Trie

Overview

A trie (prefix tree) stores strings character by character along paths from the root. Each node represents a prefix, has children for the next possible characters, and a flag marking whether a complete word ends there. Words that share a prefix share the same path.

Insert and search take O(L), where L is the word length, independent of how many words are stored. The real strength is prefix queries: finding all words that start with 'app' means walking three nodes and then collecting that subtree, which a hash set cannot do efficiently.

When to use it

• Autocomplete and 'starts with' queries.
• Many words must be searched in a grid or text at once (word search II).
• Longest common prefix, or the shortest unique prefix of words.
• Wildcard search where '.' matches any character.
• Maximum XOR of two numbers (a binary trie over bits).

Problem patterns it solves

Where it is used in real software

Key terms

Node

Holds children (map or array of 26) and an isEnd flag.

Prefix

The path from the root to a node.

isEnd

True when a stored word ends at this node.

Radix / compressed trie

Merges single-child chains into one edge labeled with a string.

How it works, step by step

1. 1
   Insert

   For each character, create the child if missing and move to it. Mark isEnd at the last node.

2. 2
   Search a word

   Follow characters; if any child is missing return false; at the end return node.isEnd.

3. 3
   startsWith

   Same walk, but return true if the path exists, regardless of isEnd.

4. 4
   Collect words under a prefix

   Walk to the prefix node, then DFS its subtree, building strings.

Insert "app", "apple", "apt", then query

Root -> a -> p -> p (end) -> l -> e (end); p -> t (end)

All three words share the nodes a and p. Every query costs only the length of the query string.

Implementation

1class TrieNode {2  constructor() {3    this.children = new Map();4    this.isEnd = false;5  }6}7 8class Trie {9  constructor() { this.root = new TrieNode(); }10 11  insert(word) {12    let node = this.root;13    for (const ch of word) {14      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());15      node = node.children.get(ch);16    }17    node.isEnd = true;18  }19 20  #walk(prefix) {21    let node = this.root;22    for (const ch of prefix) {23      node = node.children.get(ch);24      if (!node) return null;25    }26    return node;27  }28 29  search(word) { return this.#walk(word)?.isEnd === true; }30  startsWith(prefix) { return this.#walk(prefix) !== null; }31 32  suggestions(prefix, limit = 3) {33    const start = this.#walk(prefix);34    const result = [];35    const dfs = (node, path) => {36      if (result.length === limit) return;37      if (node.isEnd) result.push(path);38      for (const ch of [...node.children.keys()].sort()) dfs(node.children.get(ch), path + ch);39    };40    if (start) dfs(start, prefix);41    return result;42  }43}44 45// 211: '.' matches any character46function searchWithDots(node, word, i = 0) {47  if (i === word.length) return node.isEnd;48  if (word[i] === ".") {49    for (const child of node.children.values()) if (searchWithDots(child, word, i + 1)) return true;50    return false;51  }52  const child = node.children.get(word[i]);53  return child ? searchWithDots(child, word, i + 1) : false;54}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Returning true for search on a prefix that is not a word.

  Fix: Check isEnd at the final node.

• Duplicate results in Word Search II.

  Fix: Clear the stored word after finding it.

• Not pruning.

  Fix: Stop DFS as soon as the current prefix has no trie node.

Interview questions

Practice problems