Tries
On this page
Type "ca" into a search box and it suggests "car", "cart", "cat" before you finish. Doing that with a list of a million words means checking every word for the prefix on every keystroke. A hash set can't help either: it only answers "is this exact word here?". A trie stores words by their shared prefixes, so finding everything that starts with "ca" costs two steps plus the size of the answer, no matter how many words there are.
This page covers both the data structure and the pattern: the Trie problems in the Problems section build on it directly.
How it works
One letter per edge, shared prefixes

A trie (also called a prefix tree) is a tree where each edge stands for one character. The path from the root to a node spells a prefix. Each node holds:
children: a map from character to child node;is_end: a flag saying "a word ends here".
The flag matters: "car" and "cart" share the path c → a → r, and only the flag on r tells you that "car" itself is a word.
Insert, search, prefix search
All three walk down from the root one character at a time:
- Insert: follow existing edges, creating nodes where they're missing; set
is_endon the last node. - Search(word): follow the edges; if one is missing, the word isn't there. At the end, return
is_end. - StartsWith(prefix): the same walk, but succeed as soon as the prefix's last node exists.

Each operation costs O(L), where L is the length of the word or prefix, independent of how many words the trie holds.
Storing children

Operations and costs
| Operation | Trie | Hash set of words |
|---|---|---|
| Insert a word of length L | O(L) | O(L) to hash it |
| Exact search | O(L) | O(L) |
| Does any word start with this prefix? | O(L) | O(n · L): check every word |
| List all words with a prefix | O(L + size of the output) | O(n · L) |
| Memory | O(total characters), shared prefixes stored once | O(total characters) |
When to reach for it
- Prefix questions: autocomplete, search suggestions, "does any word start with…".
- Many words searched in a grid or text at once: build a trie of the words and walk it during a single DFS of the board, instead of searching for each word separately (Word Search II).
- Wildcards: a
.that matches any letter becomes "try every child" at that position. - Replace words by their shortest root: walk the trie and stop at the first
is_end. - Bitwise tries (one edge per bit) answer "maximum XOR with this number" questions. Rare, but worth knowing exists.
If you only need exact lookups, a hash set is simpler and just as fast.
Example
A trie with insert, search and prefix search:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def _walk(self, s):
node = self.root
for ch in s:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word):
node = self._walk(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._walk(prefix) is not None
class Trie {
private static class Node {
Map<Character, Node> children = new HashMap<>();
boolean isEnd;
}
private final Node root = new Node();
public void insert(String word) {
Node node = root;
for (char ch : word.toCharArray()) {
node = node.children.computeIfAbsent(ch, k -> new Node());
}
node.isEnd = true;
}
private Node walk(String s) {
Node node = root;
for (char ch : s.toCharArray()) {
node = node.children.get(ch);
if (node == null) return null;
}
return node;
}
public boolean search(String word) {
Node node = walk(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return walk(prefix) != null;
}
}
struct TrieNode {
unordered_map<char, TrieNode*> children;
bool isEnd = false;
};
class Trie {
TrieNode* root = new TrieNode();
TrieNode* walk(const string& s) {
TrieNode* node = root;
for (char ch : s) {
auto it = node->children.find(ch);
if (it == node->children.end()) return nullptr;
node = it->second;
}
return node;
}
public:
void insert(const string& word) {
TrieNode* node = root;
for (char ch : word) {
if (!node->children.count(ch)) node->children[ch] = new TrieNode();
node = node->children[ch];
}
node->isEnd = true;
}
bool search(const string& word) {
TrieNode* node = walk(word);
return node && node->isEnd;
}
bool startsWith(const string& prefix) { return walk(prefix) != nullptr; }
};
type TrieNode struct {
children map[rune]*TrieNode
isEnd bool
}
type Trie struct{ root *TrieNode }
func NewTrie() *Trie {
return &Trie{root: &TrieNode{children: map[rune]*TrieNode{}}}
}
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
next, ok := node.children[ch]
if !ok {
next = &TrieNode{children: map[rune]*TrieNode{}}
node.children[ch] = next
}
node = next
}
node.isEnd = true
}
func (t *Trie) walk(s string) *TrieNode {
node := t.root
for _, ch := range s {
next, ok := node.children[ch]
if !ok {
return nil
}
node = next
}
return node
}
func (t *Trie) Search(word string) bool {
node := t.walk(word)
return node != nil && node.isEnd
}
func (t *Trie) StartsWith(prefix string) bool { return t.walk(prefix) != nil }
Time: O(L) per call. Space: O(total characters inserted). After inserting car, cat, cart, do and dog: search("car") is true, search("ca") is false (no word ends there), starts_with("ca") is true.
Common mistakes
- Forgetting the end flag. Without it, every prefix of a word looks like a word.
- Search vs. starts-with. They share the walk; only the final check differs.
- Rebuilding the trie per query. Build once, query many times; that's the whole point.
- Collecting suggestions from the root. Walk to the prefix's node first, then DFS only below it.
- Memory on huge inputs. An array of 26 children per node is fast but heavy; use a map when the alphabet is large or sparse.
- In Word Search II, not pruning. Remove a word's end flag (or the leaf) after finding it, so you don't report it twice and you stop exploring dead branches.
Say this in the interview
- "A hash set can tell me if a word exists, but not if any word starts with a prefix. A trie answers both in O(length of the prefix)."
- "I'll store children in a map and an is-end flag on each node, so 'car' and 'cart' can share the path."
- "Instead of searching the board once per word, I'll put all the words in a trie and do a single DFS that follows the trie as it goes."
Used in
- Problems (Tries): Implement Trie (Prefix Tree), Design Add and Search Words Data Structure, Search Suggestions System, Replace Words, Word Search II
- Patterns: Backtracking (Word Search II combines both), Tree DFS
- Data structures: Hash Maps, Binary Trees
- System design: the same idea powers type-ahead suggestions at scale (see the System Design track's Type-ahead problem).