Trie (Prefix Tree) Complete Guide

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

How It Compares

Real-World Stories and Company Examples

Trie insert + search

type TrieNode = { isWord: boolean; children: Array<TrieNode | null> }

function createTrieNode(): TrieNode {
  return { isWord: false, children: new Array<TrieNode | null>(26).fill(null) }
}

function charIndex(char: string): number {
  return char.charCodeAt(0) - 97
}

function insertWord(rootNode: TrieNode, word: string): void {
  let currentNode = rootNode
  for (let index = 0; index < word.length; index += 1) {
    const childIndex = charIndex(word[index])
    if (!currentNode.children[childIndex]) {
      currentNode.children[childIndex] = createTrieNode()
    }
    currentNode = currentNode.children[childIndex]!
  }
  currentNode.isWord = true
}

function searchWord(rootNode: TrieNode, word: string): boolean {
  let currentNode: TrieNode | null = rootNode
  for (let index = 0; index < word.length && currentNode; index += 1) {
    currentNode = currentNode.children[charIndex(word[index])]
  }
  return Boolean(currentNode?.isWord)
}

Common Problems and Failure Modes

• Underestimating memory usage for large alphabets.
• Not cleaning unused nodes during deletion.
• Treating prefix match as full-word match without terminal checks.
• Choosing trie for tiny datasets where map is simpler.
• Using dense arrays for sparse alphabets and wasting space.

Tips and Tricks

• Trie is ideal when prefix lookups dominate workload.
• Store end-of-word flags explicitly; prefix existence is not word existence.
• Compress sparse branches (radix-like ideas) when memory is a concern.
• Use trie for many repeated queries, not one-off string checks.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

Real-system usage signals

• Prefix lookups run in O(length of query).
• Shared prefixes avoid repeated string comparisons.
• Useful for autocomplete and dictionary-style search features.

LeetCode-specific tips (including pattern-identification signals)

• Identification signal: many prefix queries over word dictionary (autocomplete, startsWith, wildcard prefix checks).
• Identification signal: repeated prefix lookups are too slow with full string scans each time.
• If the prompt combines insert/search prefix operations at scale, trie is usually stronger than plain hash-map.
• For Trie (Prefix Tree) questions, start by naming the core invariant before writing code.
• Use the constraint section to set time/space target first, then pick the data structure/algorithm.
• Solve one tiny example by hand and map each transition to your variables before implementing.
• Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
• During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.