Trie pattern

A tree of characters for fast prefix lookups.

Part 1 of 5

Basics

The idea behind the pattern, why it is correct, and the clues in a question that point to it.

1.1Core idea

What the pattern does, in plain words.

Each node is a Map of next characters plus an end-of-word flag. Inserting or searching a word costs its length, independent of how many words are stored.

Why it works

A trie stores words character by character along shared paths, so all words with the same prefix share the same first nodes. Looking up a prefix costs its length, however many words are stored.

Typical cost: O(L) per insert or lookup, O(total characters) space

1.2Recognition signals

If a question has one of these clues, try this pattern first.

Autocomplete or 'starts with'Many words searched in one gridLongest common prefixReplace words by roots
Part 2 of 5

Question

A classic interview problem from this family. Read it carefully and plan the approach before writing any code.

2.1Search Suggestions System

The problem statement, then the plan you would say out loud.

Problem

After each typed character, return up to three products with that prefix, alphabetically.

Plan before you code

  1. Sort products once.
  2. For each prefix, binary search the first match and take up to three that still match.
  3. A trie works too; sorting + binary search is shorter in an interview.
Part 3 of 5

Detailed answer

First the reusable template, then the worked solution built from it and a walk through it one step at a time.

3.1Template

Memorise this shape. Most problems in this family are this code plus one twist.

Insert and prefix search

TypeScriptKotlinJava
insert-prefix-search.tsTypeScriptCopy
1class TrieNode {2  children = new Map<string, TrieNode>();3  end = false;4}5 6class Trie {7  root = new TrieNode();8  insert(word: string): void {9    let node = this.root;10    for (const ch of word) {11      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());12      node = node.children.get(ch)!;13    }14    node.end = true;15  }16  startsWith(prefix: string): boolean {17    let node = this.root;18    for (const ch of prefix) {19      const next = node.children.get(ch);20      if (!next) return false;21      node = next;22    }23    return true;24  }25}
25 linesUTF-8TypeScript
insert-prefix-search.ktKotlinCopy
1class TrieNode {2    val children = HashMap<Char, TrieNode>()3    var end = false4}5 6class Trie {7    private val root = TrieNode()8 9    fun insert(word: String) {10        var node = root11        for (ch in word) node = node.children.getOrPut(ch) { TrieNode() }12        node.end = true13    }14 15    fun startsWith(prefix: String): Boolean {16        var node = root17        for (ch in prefix) node = node.children[ch] ?: return false18        return true19    }20}
20 linesUTF-8Kotlin
insert-prefix-search.javaJavaCopy
1class TrieNode {2  Map<Character, TrieNode> children = new HashMap<>();3  boolean end = false;4}5 6class Trie {7  TrieNode root = new TrieNode();8 9  void insert(String word) {10    TrieNode node = root;11    for (char ch : word.toCharArray()) {12      node = node.children.computeIfAbsent(ch, c -> new TrieNode());13    }14    node.end = true;15  }16 17  boolean startsWith(String prefix) {18    TrieNode node = root;19    for (char ch : prefix.toCharArray()) {20      node = node.children.get(ch);21      if (node == null) return false;22    }23    return true;24  }25}
25 linesUTF-8Java
  1. The root is an empty node; each node maps a character to its child.
  2. Walk or create one node per character, then mark the end of the word.
  3. A prefix exists if every character has a node.

3.2Solution

Strict TypeScript, type-checked and tested.

Search Suggestions System

TypeScriptKotlinJava
search-suggestions-system.tsTypeScriptCopy
1function suggestedProducts(products: string[], word: string): string[][] {2  products.sort();3  const out: string[][] = [];4  let prefix = "";5  for (const ch of word) {6    prefix += ch;7    let lo = 0, hi = products.length;   // first product >= prefix8    while (lo < hi) {9      const mid = (lo + hi) >> 1;10      if (products[mid] < prefix) lo = mid + 1;11      else hi = mid;12    }13    out.push(products.slice(lo, lo + 3).filter((p) => p.startsWith(prefix)));14  }15  return out;16}
16 linesUTF-8TypeScript
search-suggestions-system.ktKotlinCopy
1fun suggestedProducts(products: Array<String>, word: String): List<List<String>> {2    products.sort()3    val out = mutableListOf<List<String>>()4    var prefix = ""5    for (ch in word) {6        prefix += ch7        var lo = 08        var hi = products.size   // first product >= prefix9        while (lo < hi) {10            val mid = (lo + hi) ushr 111            if (products[mid] < prefix) lo = mid + 112            else hi = mid13        }14        out.add(products.slice(lo until minOf(lo + 3, products.size)).filter { it.startsWith(prefix) })15    }16    return out17}
17 linesUTF-8Kotlin
search-suggestions-system.javaJavaCopy
1static List<List<String>> suggestedProducts(String[] products, String word) {2  Arrays.sort(products);3  List<List<String>> out = new ArrayList<>();4  StringBuilder prefix = new StringBuilder();5  for (char ch : word.toCharArray()) {6    prefix.append(ch);7    String p = prefix.toString();8    int lo = 0, hi = products.length;   // first product >= prefix9    while (lo < hi) {10      int mid = (lo + hi) >>> 1;11      if (products[mid].compareTo(p) < 0) lo = mid + 1;12      else hi = mid;13    }14    List<String> hits = new ArrayList<>();15    for (int i = lo; i < Math.min(lo + 3, products.length); i++) {16      if (products[i].startsWith(p)) hits.add(products[i]);17    }18    out.add(hits);19  }20  return out;21}
21 linesUTF-8Java

Step by step

  1. Sort once: words sharing a prefix sit together.
  2. Binary search the first word ≥ the prefix.
  3. Take up to three that still match.

Complexity: O(n log n + L log n) time

Part 4 of 5

Q&A

What interviewers ask once your code works, and problems to try on your own.

4.1Interview questions

Answer out loud, then open.

Trie or hash set?
A hash set answers 'is this exact word present?'. A trie also answers prefix questions and can list the completions.
How much memory does it use?
One node per distinct prefix. A Map per node stays compact for large alphabets; a 26-slot array per node is faster for lowercase letters.
How do you return the top suggestions quickly?
Keep a small sorted list or counts at each node, or sort the words once and binary search, as the worked problem does.

4.2Solo practice

Try these without looking; open the hint only when stuck.

MediumReplace Words
Hint

Walk each word until you hit an end flag.

Part 5 of 5

Extra depth

More fully worked problems in the same family, and the mistakes that cost offers.

5.12 more worked problems

Each one: the problem, the plan, the code and its cost.

Show detailsHide details
Medium

Implement Trie

Support insert, search (whole word) and startsWith.

  1. Nested dicts, one level per character.
  2. A '$' key marks the end of a word.
  3. search and startsWith share one walk.
implement-trie.tsTypeScriptCopy
1class TrieNode {2  children = new Map<string, TrieNode>();3  end = false;4}5 6class Trie {7  private root = new TrieNode();8  insert(word: string): void {9    let node = this.root;10    for (const ch of word) {11      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());12      node = node.children.get(ch)!;13    }14    node.end = true;15  }16  private walk(s: string): TrieNode | null {17    let node: TrieNode | undefined = this.root;18    for (const ch of s) {19      node = node.children.get(ch);20      if (!node) return null;21    }22    return node;23  }24  search(word: string): boolean {25    return this.walk(word)?.end === true;26  }27  startsWith(prefix: string): boolean {28    return this.walk(prefix) !== null;29  }30}
30 linesUTF-8TypeScript

Complexity: O(L) per operation

Hard

Word Search II

Find every dictionary word that can be traced in a letter grid.

  1. Build a trie of the words.
  2. DFS from every cell, following trie edges only.
  3. Remove found words and dead branches to prune later searches.
word-search-ii.tsTypeScriptCopy
1type WordNode = { kids: Map<string, WordNode>; word?: string };2 3function findWords(board: string[][], words: string[]): string[] {4  const root: WordNode = { kids: new Map() };5  for (const w of words) {6    let node = root;7    for (const ch of w) {8      if (!node.kids.has(ch)) node.kids.set(ch, { kids: new Map() });9      node = node.kids.get(ch)!;10    }11    node.word = w;12  }13  const rows = board.length, cols = board[0].length, found: string[] = [];14  const dfs = (r: number, c: number, parent: WordNode): void => {15    const ch = board[r][c];16    const node = parent.kids.get(ch);17    if (!node) return;18    if (node.word !== undefined) {19      found.push(node.word);20      node.word = undefined;   // collect each word once21    }22    board[r][c] = "#";23    for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {24      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== "#") dfs(nr, nc, node);25    }26    board[r][c] = ch;27    if (node.kids.size === 0 && node.word === undefined) parent.kids.delete(ch);28  };29  for (let r = 0; r < rows; r++) {30    for (let c = 0; c < cols; c++) dfs(r, c, root);31  }32  return found;33}
33 linesUTF-8TypeScript

Complexity: O(cells · 4^L) worst case; pruning makes it fast in practice

5.2Traps

Bugs and misreadings that come up again and again with this pattern.

Show detailsHide details
  • Forgetting the end-of-word marker
  • Rebuilding the trie per query