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 the root to nodes form prefixes of the stored words. The root node is empty — it represents the empty string.
Unlike a hash map that stores complete words, a trie shares prefixes. The words "app", "apple", and "apt" share the path a → p. This shared structure is what makes tries efficient for prefix queries: instead of scanning every word in a dictionary, you walk down the tree one character at a time.
The key insight: common prefixes are stored once. If you have 10,000 words starting with "pre", the trie stores "p → r → e" just once and branches from there. This makes prefix-based operations — autocomplete, spell checking, IP routing — extremely fast.
Trie Built from ["app", "apple", "apt", "bat", "bar"]
Notice how "app" and "apple" share the path root → a → p → p. The green nodes mark where complete words end. The node for the second "p" is green because "app" is a word, even though the path continues to "apple".
TrieNode Structure
Every node in a trie has two things: a dictionary of child nodes (one entry per character that continues from here) and a boolean flag indicating whether this node marks the end of a complete word.
Why a dictionary for children?
- Flexibility: A dictionary maps each character to its child node. You don't need to pre-allocate 26 slots (or more for Unicode) — only characters that actually appear get stored.
- Lookup: Checking if a character exists is O(1) on average with a hash map.
- Alternative: Some implementations use a fixed-size array of 26 entries (for lowercase English letters). This trades memory for slightly faster lookups since array indexing is faster than hashing.
Implement Trie — Insert, Search, StartsWith
The Trie class wraps a root TrieNode and provides three core operations. This is LeetCode 208 — one of the most frequently asked data structure design problems.
How each method works
insert(word)— Walk character by character from the root. If a child for the current character doesn't exist, create a new TrieNode. After the last character, markis_end = True.search(word)— Walk the trie following the word's characters. If any character is missing, return False. If you reach the end, checkis_end— the word exists only if this node marks a complete word.starts_with(prefix)— Same walk as search, but you don't checkis_end. If you can follow all characters without hitting a dead end, the prefix exists._find(prefix)— Shared helper that walks the trie and returns the node at the end of the prefix (or None). Bothsearchandstarts_withuse this to avoid code duplication.
Autocomplete — Find All Words with a Prefix
This is where tries truly shine. Given a prefix, return all stored words that start with it. This is exactly what happens when you type in a search bar and see suggestions appear.
How autocomplete works
- Navigate to the prefix node — Use
_find(prefix)to walk to the node representing the last character of the prefix. If the prefix doesn't exist in the trie, return an empty list. - DFS from that node — From the prefix node, explore all descendants using depth-first search. Every time you reach a node where
is_end = True, you've found a complete word — addprefix + pathto results. - Build the path as you go — Each recursive call appends the current character to the path string, building up the suffix that completes the word.
Space vs Time Trade-off
Tries trade memory for speed. Understanding this trade-off is critical for interviews — it shows you think beyond just time complexity.
- Hash Set search: O(m) average (hash the word, then compare) — but no prefix support. To find all words starting with "app", you'd scan every word in the set.
- Trie search: O(m) guaranteed — walk m characters down the tree. Plus, prefix queries like
starts_withandautocompleteare natural and fast. - Memory: A trie node stores a dictionary of children + a boolean. For sparse data (few shared prefixes), this overhead can exceed a hash set. For dense data (many shared prefixes), the trie can actually use less total space than storing full strings.
When tries use more memory
Consider storing ["cat", "dog", "fish"]. These words share no prefixes, so the trie creates one node per character — 10 nodes, each with a dictionary. A hash set stores 3 strings with less overhead. Tries shine when there's heavy prefix sharing: storing 10,000 English words starting with "un-" reuses the u → n path 10,000 times.
When to Use Tries
Tries appear across system design and coding interviews. Recognise these patterns and you'll know when to reach for a trie:
- Autocomplete / Type-ahead: "Design a search suggestion system" — trie is the textbook answer. Google, YouTube, and Amazon all use trie-like structures for search suggestions.
- Spell checker: Check if a word exists in a dictionary, suggest corrections by exploring nearby paths in the trie.
- IP routing: Routers use tries to match IP addresses against routing tables. The longest prefix match determines where a packet goes.
- Word games: Scrabble solvers and Boggle checkers use tries to quickly validate words and prune invalid paths on the board.
- Prefix count: "How many words in the dictionary start with 'pre'?" — walk to the "pre" node and count descendants.
- Longest common prefix: Walk the trie from the root until a node has more than one child — that path is the longest shared prefix (LeetCode 14).
Try It Yourself
Implement a Trie with Insert, Search, StartsWith
Complete the Trie class below. Implement insert, search, and starts_with. The test cases will verify your implementation.
Challenge
Given a 2D board of characters and a list of words, find all words that can be formed by sequentially adjacent cells (horizontally or vertically). Each cell may only be used once per word.
Example: Board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], Words = ["oath","pea","eat","rain"]. Answer: ["oath","eat"].
Why a trie? Instead of searching the board for each word separately, build a trie from the word list and search the board once — pruning branches that don't match any prefix in the trie.
is_end = True, you found a word — add it to results and set is_end = False to avoid duplicates. Backtrack by unmarking the cell when you return.Quiz
search("app") from starts_with("app") in a trie?You've mastered prefix trees.
Now build the career they power.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →