Trie (Prefix Tree) Complete Guide

Data Structure • hard

Trie is a prefix tree where each edge represents a character and shared prefixes are stored once.

It is optimized for prefix queries, autocomplete, dictionary checks, and lexicographic traversal tasks.

Trie trades extra memory for fast prefix operations.

Typical Complexity Baseline

Metric	Value
Insert/search prefix	`O(length of word)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Trie prefix tree of characters

Words "cat" and "car" share the path c → a, then split into different leaves.

Step 1/13Empty trie just the root.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Data Structures: Tries

Channel: HackerRank

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Root node

What it is Entry node with no character.

Why it matters Root node is a required building block for understanding how Trie (Prefix Tree) stays correct and performant on large inputs.

Children map

What it is Character -> next node mapping.

Why it matters Children map is a required building block for understanding how Trie (Prefix Tree) stays correct and performant on large inputs.

End marker

What it is Flag marking completed word.

Why it matters End marker is a required building block for understanding how Trie (Prefix Tree) stays correct and performant on large inputs.

Prefix path

What it is Node path representing query prefix.

Why it matters Prefix path is a required building block for understanding how Trie (Prefix Tree) stays correct and performant on large inputs.

Optional payload

What it is Metadata stored at terminal nodes.

Why it matters Optional payload is a required building block for understanding how Trie (Prefix Tree) stays correct and performant on large inputs.

Prefix

What it is Starting substring of a word.

Why it matters Starting substring of a word. In Trie (Prefix Tree), this definition helps you reason about correctness and complexity when inputs scale.

Terminal node

What it is Node representing end of a valid word.

Why it matters Node representing end of a valid word. In Trie (Prefix Tree), this definition helps you reason about correctness and complexity when inputs scale.

Compressed trie

What it is Trie variant collapsing single-child paths.

Why it matters Trie variant collapsing single-child paths. In Trie (Prefix Tree), this definition helps you reason about correctness and complexity when inputs scale.

Radix tree

What it is Space-optimized trie with merged edges.

Why it matters Space-optimized trie with merged edges. In Trie (Prefix Tree), this definition helps you reason about correctness and complexity when inputs scale.

Branching factor

What it is Average number of children per node.

Why it matters Average number of children per node. In Trie (Prefix Tree), this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/13

Empty trie just the root.

Step 2/13

Insert 'cat': create 'c' under root.

Step 3/13

Create 'a' under 'c'.

Step 4/13

Create 't' and mark terminal. 'cat' done.

Step 5/13

Insert 'car': walk c → a (both exist reuse).

Step 6/13

Branch off with 'r' and mark terminal. 'car' done.

Step 7/13

Insert 'card': walk c → a → r (reuse all).

Step 8/13

Create 'd' and mark terminal. 'card' shares the entire 'car' prefix.

Step 9/13

Insert 'cars': walk c → a → r (reuse).

Step 10/13

Create 's' as another child of r. Mark terminal.

Step 11/13

Insert 'dog': totally new branch under root. Create 'd'.

Step 12/13

Create 'o' under 'd'.

Step 13/13

Create 'g' and mark terminal. 5 words stored, common prefixes shared. Lookup is O(L) where L = word length.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Hash map of full strings

Choose this when Choose trie for frequent prefix queries.

Tradeoff Hash map is simpler and often lighter for exact-match only.

vs. Sorted array + binary search

Choose this when Choose trie when many prefix checks are needed online.

Tradeoff Sorted arrays can be more memory-efficient for static dictionaries.

vs. Suffix array/tree

Choose this when Choose trie for prefix-oriented lookups.

Tradeoff Suffix structures target substring search across whole text.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Google

Autocomplete-style systems rely on prefix indexing strategies closely related to trie behavior.

Takeaway Prefix-first retrieval is the core value proposition.

VS Code ecosystem

Code completion engines maintain prefix-indexed symbol data for fast suggestion filtering.

Takeaway Trie-like indexing improves developer UX latency.

Cloudflare

Domain and rule matching systems benefit from prefix tree structures for hierarchical matching.

Takeaway Trie structures map naturally to hierarchical token spaces.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Implement nodes and child slots directly so prefix-tree behavior is fully explicit without built-in hash maps.

Complexity: Time O(L) per insert/search, L = word length

Trie insert + search

Language

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)
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

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.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

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.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

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 (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.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Longest Common Prefix	Easy	`O(n*m)`
2	Implement Trie (Prefix Tree)	Medium	`O(L)`
3	Design Add and Search Words Data Structure	Medium	`O(L)` avg
4	Replace Words	Medium	`O(total chars)`
5	Map Sum Pairs	Medium	`O(L)`
6	Maximum XOR of Two Numbers in an Array	Medium	`O(n * bits)`
7	Word Search II	Hard	Pruned DFS
8	Palindrome Pairs	Hard	`O(n*k^2)`
9	Stream of Characters	Hard	`O(L)` per query
10	Word Squares	Hard	Backtracking + trie