Introduction to Trie

A trie (pronounced "try") is a tree-like data structure used for storing strings. It's also called a prefix tree because it excels at prefix-based operations.

Imagine you have a dictionary of words and need to:

Check if a word exists
Find all words starting with a prefix
Implement autocomplete

A hash set can check if a word exists in O(1), but finding all words with a prefix requires checking every word. A trie solves this efficiently.

Each node in a trie represents a character. The path from the root to a node spells out a prefix. Nodes are marked as "end of word" when they complete a valid word.

Operation	Hash Set	Trie
Check if word exists	O(m)	O(m)
Check if prefix exists	O(n * m)	O(m)
Find all words with prefix	O(n * m)	O(m + k)
Autocomplete suggestions	O(n * m)	O(m + k)

n = number of words, m = length of word/prefix, k = number of matching words

Use a Trie when:

You need prefix-based search or autocomplete
You're doing word validation (like in word games)
You need to find words matching a pattern

Use a Hash Set when:

You only need exact word lookup
You don't care about prefixes
Memory is a concern (tries can use more memory)

Implement Trie: Build insert, search, and startsWith operations
Word Search II: Find all words from a dictionary in a grid
Autocomplete System: Return top suggestions for a prefix
Replace Words: Replace words with their shortest prefix in dictionary

Was this helpful?

Study plan All problems

Cheat Sheet

What Problem Does a Trie Solve?

Trie Structure

Why Use a Trie?

Trie vs Other Data Structures

Common Interview Problems

Company

Practice

Learn