Trie Data Structure: Complete Interview Guide

What is a Trie?

A trie (pronounced "try") is a tree-like data structure that stores strings character by character. Each node represents a single character, and paths from root to leaf (or marked nodes) represent complete words. The key advantage: prefix lookups are O(m) where m is the prefix length, regardless of how many words are stored.

When to Use a Trie

• Autocomplete / typeahead: Find all words starting with a prefix
• Spell checking: Check if a word exists, suggest corrections
• Word search in grids: Efficiently prune search paths
• IP routing: Longest prefix matching
• Dictionary operations: Insert, search, prefix search in O(m) time

If the problem involves prefixes, word lookups, or building words character by character, think trie.

Basic Trie Implementation

class TrieNode {
  children: Map<string, TrieNode> = new Map()
  isEndOfWord: boolean = false
}

class Trie {
  root: TrieNode = new TrieNode()

  // Insert a word - O(m) time, O(m) space
  insert(word: string): void {
    let node = this.root
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode())
      }
      node = node.children.get(char)!
    }
    node.isEndOfWord = true
  }

  // Search for exact word - O(m) time
  search(word: string): boolean {
    const node = this.findNode(word)
    return node !== null && node.isEndOfWord
  }

  // Check if any word starts with prefix - O(m) time
  startsWith(prefix: string): boolean {
    return this.findNode(prefix) !== null
  }

  // Helper: traverse to the node for a given string
  private findNode(str: string): TrieNode | null {
    let node = this.root
    for (const char of str) {
      if (!node.children.has(char)) return null
      node = node.children.get(char)!
    }
    return node
  }
}

Pattern 1: Autocomplete / Prefix Search

Problem: Given a dictionary of words and a prefix, return all words that start with that prefix.

function autocomplete(trie: Trie, prefix: string): string[] {
  const results: string[] = []
  const node = trie.findNode(prefix)
  if (!node) return results

  // DFS to collect all words from this node
  function dfs(node: TrieNode, path: string) {
    if (node.isEndOfWord) {
      results.push(path)
    }
    for (const [char, child] of node.children) {
      dfs(child, path + char)
    }
  }

  dfs(node, prefix)
  return results
}

// Usage:
// trie has: ["apple", "app", "application", "banana"]
// autocomplete(trie, "app") → ["app", "apple", "application"]

Pattern 2: Word Search II (LeetCode 212)

Problem: Given a 2D board of characters and a list of words, find all words that can be formed by adjacent cells (up, down, left, right).

This is where tries shine - instead of searching for each word separately (slow), build a trie from all words and search the grid once.

function findWords(board: string[][], words: string[]): string[] {
  const trie = new Trie()
  for (const word of words) trie.insert(word)

  const results = new Set<string>()
  const rows = board.length, cols = board[0].length

  function dfs(r: number, c: number, node: TrieNode, path: string) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return
    const char = board[r][c]
    if (char === '#' || !node.children.has(char)) return

    const next = node.children.get(char)!
    const newPath = path + char

    if (next.isEndOfWord) {
      results.add(newPath)
      // Don't return - there might be longer words
    }

    board[r][c] = '#' // mark visited
    dfs(r + 1, c, next, newPath)
    dfs(r - 1, c, next, newPath)
    dfs(r, c + 1, next, newPath)
    dfs(r, c - 1, next, newPath)
    board[r][c] = char // restore

    // Optimization: prune empty branches
    if (next.children.size === 0) {
      node.children.delete(char)
    }
  }

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

  return [...results]
}

// Key insight: trie lets us prune entire search branches.
// Without trie: O(words * cells * 4^wordLen)
// With trie: O(cells * 4^maxLen) - search all words simultaneously

Pattern 3: Design Add and Search Words (LeetCode 211)

Problem: Support adding words and searching with '.' wildcards, where '.' matches any character.

class WordDictionary {
  root: TrieNode = new TrieNode()

  addWord(word: string): void {
    let node = this.root
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode())
      }
      node = node.children.get(char)!
    }
    node.isEndOfWord = true
  }

  search(word: string): boolean {
    return this.dfs(word, 0, this.root)
  }

  private dfs(word: string, index: number, node: TrieNode): boolean {
    if (index === word.length) return node.isEndOfWord

    const char = word[index]

    if (char === '.') {
      // Wildcard: try all children
      for (const child of node.children.values()) {
        if (this.dfs(word, index + 1, child)) return true
      }
      return false
    }

    if (!node.children.has(char)) return false
    return this.dfs(word, index + 1, node.children.get(char)!)
  }
}

// addWord("bad"), addWord("dad"), addWord("mad")
// search(".ad") → true (matches all three)
// search("b..") → true (matches "bad")
// search("b.d") → true (matches "bad")

Trie Complexity Analysis

Optimization: Array vs Map Children

For lowercase English letters only, use a fixed array of 26 instead of a Map. This is faster (array index vs hash lookup) and uses less memory per node.

class TrieNodeArray {
  children: (TrieNodeArray | null)[] = new Array(26).fill(null)
  isEndOfWord: boolean = false
}

// Access: node.children[char.charCodeAt(0) - 97]
// 'a' = index 0, 'b' = index 1, ..., 'z' = index 25
// Faster than Map for known alphabet, but wastes space for sparse nodes

Problems to Practice

• Implement Trie (LeetCode 208) - Start here. Core insert/search/startsWith
• Word Search II (LeetCode 212) - Hard. Trie + backtracking on grid
• Design Search Autocomplete (LeetCode 642) - Trie with frequency ranking
• Add and Search Word (LeetCode 211) - Trie with wildcard DFS
• Replace Words (LeetCode 648) - Find shortest prefix root
• Maximum XOR (LeetCode 421) - Bitwise trie, advanced