Trees
Trie Fundamentals
A trie (prefix tree) is a tree-shaped data structure where each edge represents a character and each path from root to a marked node represents a stored word. Insert and search both run in O(L) where L is the word length — independent of how many words are stored. Tries power autocomplete, spell checkers, IP routing tables, and word-search/boggle-style interview problems.
01
Section One · Foundation
What is Trie?
A trie is an n-ary tree where each node represents a character and paths from root to marked nodes spell out stored words. The key insight: shared prefixes share nodes. “cat” and “car” share the path c→a, then branch at the third character. This makes prefix-based operations (autocomplete, starts-with) extremely efficient — O(P) for any prefix of length P, regardless of how many words are in the trie.
Each node typically has:
Array-Based Node
children[26]
Each node has a fixed-size array of 26 pointers (for lowercase English). Fast O(1) child lookup but wastes space for sparse nodes.
- O(1) child access
- 26 × pointer size per node
- Best for lowercase-only dictionaries
HashMap-Based Node
children: Map
Each node has a HashMap of character → child. Space-efficient for large alphabets (Unicode) but slightly slower child lookup.
- Supports any character set
- Memory-efficient for sparse tries
- Slightly more overhead per access
Analogy: A phone directory tree. The first letter narrows you to one section, the second letter to a sub-section, and so on. By the time you’ve traced 5 letters, you’re looking at a tiny slice — no matter if the directory has 10 or 10 million entries. That’s why autocomplete feels instant.
Key Characteristics
Each edge = one character
▶
Root-to-node path spells a prefix
Shared prefixes share nodes
▶
Space-efficient for words with common beginnings
Insert/search = walk the path
▶
O(L) where L = word length — independent of dictionary size
Boolean
isEnd flag at nodes▶
Distinguishes complete words from mere prefixes
No hashing involved
▶
No collisions — guaranteed O(L) worst case
02
Section Two · Operations
Core Operations
Insert
Walks the trie character by character, creating child nodes as needed, and marks the final node as a word end.
Pseudocode
function insert(trie, word):
node = trie.root
for ch in word:
if ch not in node.children:
node.children[ch] = new TrieNode()
node = node.children[ch]
node.isEnd = true // mark as complete word // O(L) where L = word.length
The
isEnd flag is essential. Without it, you can’t distinguish “cat” (a word) from “ca” (just a prefix of “cat”). Every insert must mark the final node. Some implementations use a count instead of a boolean to track how many times a word was inserted.Search
Walks the trie character by character; returns true only if the full path exists AND the final node is marked as a word end.
Pseudocode
function search(trie, word):
node = trie.root
for ch in word:
if ch not in node.children:
return false // path doesn’t exist
node = node.children[ch]
return node.isEnd // must be a complete word
Search and startsWith differ only in the last line. Search checks
node.isEnd; startsWith just returns true if the path exists. Many interview problems (word search, autocomplete) only need the prefix check.Starts With (Prefix Search)
Walks the trie for the prefix; returns true if the path exists — regardless of whether it’s a complete word.
Pseudocode
function startsWith(trie, prefix):
node = trie.root
for ch in prefix:
if ch not in node.children:
return false
node = node.children[ch]
return true // prefix exists — O(P)
Prefix matching is the trie’s superpower. A HashMap can check if a full word exists in O(1), but checking if any word starts with a given prefix requires scanning all keys — O(n). A trie does it in O(P) where P is the prefix length. This is why tries are used for autocomplete.
Word Search Pattern (DFS + Trie)
Combines DFS grid traversal with a trie to efficiently find all dictionary words in a character grid — the “Word Search II” pattern.
Pseudocode
function findWords(board, words):
trie = buildTrie(words)
results = []
for each cell (r, c) in board:
dfs(board, r, c, trie.root, results)
return results
function dfs(board, r, c, node, results):
ch = board[r][c]
if ch not in node.children: return
node = node.children[ch]
if node.word: // found a complete word
results.add(node.word)
node.word = null // de-duplicate
board[r][c] = '#' // mark visited for (dr, dc) in directions:
dfs(board, r+dr, c+dc, node, results)
board[r][c] = ch // unmark
Trie prunes impossible paths early. Without a trie, you’d check each word independently against the grid — O(W × M × N × 4^L). With a trie, all words share prefixes, and you abandon a DFS path the moment the trie says “no word starts this way.” This is the key insight for Word Search II.
Common Mistake: Forgetting to check
isEnd in search. If you only check that the path exists, “ca” would return true when only “cat” was inserted. Always distinguish complete words from prefixes.03
Section Three · Visuals
Diagrams & Structure
Trie Structure — Shared Prefixes
Words: “app”, “apple”, “api”, “bat” — shared prefix “ap” saves nodes
Insert & Search Walkthrough
Insert “ace”, then search “ace” (found) vs “ac” (prefix only)
Autocomplete — Prefix “ap”
startsWith(“ap”) navigates to node, then DFS collects all words below
04
Section Four · Code
Java Quick Reference
The standard Trie with insert, search, and startsWith — LeetCode 208.
Java — Trie (array-based)
class Trie {
private Trie[] children = new Trie[26];
private boolean isEnd;
void insert(String word) { // O(L) Trie node = this;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null)
node.children[i] = new Trie();
node = node.children[i];
}
node.isEnd = true;
}
boolean search(String word) { // O(L) Trie n = find(word);
return n != null && n.isEnd;
}
boolean startsWith(String pre) { // O(P) return find(pre) != null;
}
private Trie find(String s) {
Trie node = this;
for (char c : s.toCharArray()) {
node = node.children[c - 'a'];
if (node == null) return null;
}
return node;
}
}
Trie — Full Implementation
Java — Trie with delete & autocomplete
class Trie {
private Trie[] ch = new Trie[26];
private boolean end;
void insert(String w) {
Trie n = this;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (n.ch[i] == null) n.ch[i] = new Trie();
n = n.ch[i];
}
n.end = true;
}
boolean search(String w) {
Trie n = find(w);
return n != null && n.end;
}
boolean startsWith(String p) {
return find(p) != null;
}
private Trie find(String s) {
Trie n = this;
for (char c : s.toCharArray()) {
n = n.ch[c - 'a'];
if (n == null) return null;
}
return n;
}
// Autocomplete: collect all words under a prefix List<String> autocomplete(String prefix) {
List<String> res = new ArrayList<>();
Trie node = find(prefix);
if (node != null) dfs(node, new StringBuilder(prefix), res);
return res;
}
private void dfs(Trie n, StringBuilder sb, List<String> res) {
if (n.end) res.add(sb.toString());
for (int i = 0; i < 26; i++) {
if (n.ch[i] != null) {
sb.append((char)('a' + i));
dfs(n.ch[i], sb, res);
sb.deleteCharAt(sb.length() - 1);
}
}
}
}
Python — Trie with dict nodes
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:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True def search(self, word):
n = self._find(word)
return n is not None and n.is_end
def starts_with(self, prefix):
return self._find(prefix) is not None def _find(self, s):
node = self.root
for ch in s:
if ch not in node.children: return None
node = node.children[ch]
return node
def autocomplete(self, prefix):
node = self._find(prefix)
if not node: return []
results = []
def dfs(n, path):
if n.is_end: results.append(path)
for ch, child in n.children.items():
dfs(child, path + ch)
dfs(node, prefix)
return results
JavaScript — Trie (ES6 Map)
class TrieNode {
constructor() { this.children = new Map(); this.isEnd = false; }
}
class Trie {
constructor() { this.root = new TrieNode(); }
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch))
node.children.set(ch, new TrieNode());
node = node.children.get(ch);
}
node.isEnd = true;
}
search(word) {
const n = this._find(word);
return n !== null && n.isEnd;
}
startsWith(prefix) { return this._find(prefix) !== null; }
_find(s) {
let node = this.root;
for (const ch of s) {
if (!node.children.has(ch)) return null;
node = node.children.get(ch);
}
return node;
}
}
C# — Trie (Dictionary)
using System.Collections.Generic;
public class Trie {
class Node {
internal Dictionary<char, Node> ch = new();
internal bool end;
}
readonly Node root = new();
public void Insert(string word) {
var n = root;
foreach (char c in word) {
if (!n.ch.ContainsKey(c)) n.ch[c] = new Node();
n = n.ch[c];
}
n.end = true;
}
public bool Search(string w) {
var n = Find(w);
return n != null && n.end;
}
public bool StartsWith(string p) => Find(p) != null;
Node? Find(string s) {
var n = root;
foreach (char c in s) {
if (!n.ch.TryGetValue(c, out var next)) return null;
n = next;
}
return n;
}
}
05
Section Five · Complexity
Time & Space Complexity
| Operation | Time | Space |
|---|---|---|
| Insert | O(L) | O(L) new nodes |
| Search | O(L) | O(1) |
| StartsWith | O(P) | O(1) |
| Delete | O(L) | O(1) |
| Autocomplete | O(P + K) | O(K) results |
Why these complexities? Each operation walks at most L characters, doing O(1) work per character (array index or hash lookup). Time is independent of the number of words N — only the word length L matters. This is the trie’s advantage over HashMap (which also needs O(L) to hash the key but can’t do prefix matching).
Space Complexity Note
Worst case: O(N × L × Σ) where N = words, L = avg length, Σ = alphabet size (26 pointers per node for array-based). In practice, shared prefixes reduce this significantly. HashMap-based nodes use less space for sparse tries. For English dictionaries, a trie typically uses less space than storing all words individually because prefixes are shared.
06
Section Six · Decision Guide
When to Use Trie
Use This When
- Prefix-based operations — autocomplete, search suggestions, IP routing, phone directory.
- Word Search / Boggle — DFS + trie prunes impossible paths early.
- Spell checking — check if a word exists, find closest matches by edit distance.
Avoid When
- Only need exact-match lookup — a HashMap is simpler and faster for pure contains/get.
- Large alphabet — Unicode tries waste memory; use HashMap-based nodes or other structures.
Comparison
| Structure | Exact Search | Prefix Search | Space | Best For |
|---|---|---|---|---|
| Trie ← this | O(L) | O(P) ✓ | O(N·L·Σ) | Autocomplete, word search, prefix matching |
| HashMap | O(L) hash | O(N) scan ✗ | O(N·L) | Exact key lookup, frequency counting |
| Sorted Array | O(L log N) | O(L log N) | O(N·L) | Static dictionary, binary search |
07
Section Seven · Interview Practice
LeetCode Problems
Trie problems fall into two categories: implementation (build a trie with insert/search/startsWith) and application (use a trie to optimise DFS word search, autocomplete, or XOR-based problems). If the problem involves prefixes, multiple word lookups, or character-by-character matching, a trie is likely the right tool.
- MediumImplement Trie (Prefix Tree) — Build insert, search, startsWith from scratch — the foundational problem.
- MediumReplace Words — Build a trie of roots; for each word find the shortest prefix in the trie.
- MediumDesign Add and Search Words — Trie + backtracking for wildcard “.” characters.
- HardWord Search II — DFS on grid + trie of dictionary words — prune paths the trie rejects.
- HardPalindrome Pairs — Trie of reversed words; for each word check if any suffix forms a palindrome.
Interview Pattern: If a problem involves searching for multiple words or checking prefixes across many strings, build a trie first. The upfront O(N·L) build cost pays for itself when you need to check thousands of words — each check is O(L) instead of O(N).