Prefix tree for O(L) string insert/search and autocomplete problems.
A Trie (prefix tree) stores strings as paths from root to leaf. Each node represents one character. Insert and search run in O(L) where L is the word length. Tries excel at prefix queries, autocomplete, and word-existence checks on large dictionaries.
Insert/Search O(L) where L is word length
O(total characters in all words)
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this as the building block of all trie problems
Each node holds a map (or fixed-size array) from characters to child nodes and an isEnd flag that marks word boundaries. Using a Map keeps memory proportional to actual children, while a 26-element array gives O(1) array indexing for lowercase English letters.
Problem Implement Trie. Define a TrieNode with children = new Map() and isEnd = false, then build insert and search on top of it. class TrieNode { constructor() { this.children = new Map(); this.isEnd = false; } }
// Trie node structure
class TrieNode {
constructor() {
this.children = new Map();
this.isEnd = false;
}
}
class Trie {
constructor() { this.root = new TrieNode(); }
}Use this whenever you need to add a word to the trie
Walk the trie character by character: if the current character has no child node, create one and attach it. After processing all characters, mark the final node as the end of a word. This runs in O(L) where L is the word length.
Problem Implement Trie (insert). For each character, create a child node if absent, then advance the pointer.
// Insert a word into the trie
function 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;
}Use this when you need to check whether an exact word exists in the trie
Walk the trie character by character; if any character is missing, return false. After processing all characters, return the isEnd flag of the final node, because a node can exist due to a longer word without the current word being stored.
Problem Implement Trie (search). Traverse all characters; return false if any node is missing; return node.isEnd at the end.
// Search an exact word in the trie
function search(word) {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch);
}
return node.isEnd;
}Use this when you need to determine whether any inserted word begins with a given prefix, such as for autocomplete validation
The traversal is identical to search, but instead of checking isEnd at the end, you return true as long as all prefix characters have matching nodes in the trie.
Problem Implement Trie (startsWith). Walk to the end of the prefix and return true if all nodes exist; no isEnd check needed.
// Prefix check — startsWith
function startsWith(prefix) {
let node = this.root;
for (const ch of prefix) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch);
}
return true; // no isEnd check needed
}Use this when the problem asks you to find all words from a dictionary that appear in a 2-D board
Build a trie from the dictionary, then run DFS from each cell. Prune the DFS early by checking the trie node: if the current character has no child in the trie, stop. When you reach a node with isEnd set, record the word.
Problem Word Search II. At each DFS step, move to the trie child matching the cell character; if the child has isEnd, add the word to results; mark cells visited by temporarily modifying the board.
// Word Search II — trie + DFS on board
function findWords(board, words) {
const root = new TrieNode();
// build trie
for (const w of words) {
let n = root;
for (const ch of w) { if (!n.children.has(ch)) n.children.set(ch, new TrieNode()); n = n.children.get(ch); }
n.isEnd = w;
}
const res = [], rows = board.length, cols = board[0].length;
function dfs(node, r, c) {
if (node.isEnd) { res.push(node.isEnd); node.isEnd = false; }
if (r < 0 || r >= rows || c < 0 || c >= cols) return;
const ch = board[r][c];
if (ch === "#" || !node.children.has(ch)) return;
board[r][c] = "#";
const next = node.children.get(ch);
dfs(next, r-1, c); dfs(next, r+1, c); dfs(next, r, c-1); dfs(next, r, c+1);
board[r][c] = ch;
}
for (let r = 0; r < rows; r++) for (let c = 0; c < cols; c++) dfs(root, r, c);
return res;
}Use this when words may contain wildcard characters (typically "." matching any letter) that require branching
At a regular character, follow the usual trie path. At a wildcard, recursively search all existing children. This is more efficient than brute-force because the trie prunes entire subtrees at mismatching characters.
Problem Design Add and Search Words Data Structure. For search, recurse normally on letters; on a dot, recurse into all children nodes.
// Wildcard search — Add and Search Words Data Structure
class WordDictionary {
constructor() { this.root = new TrieNode(); }
addWord(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, node = this.root, idx = 0) {
if (idx === word.length) return node.isEnd;
const ch = word[idx];
if (ch !== ".") {
if (!node.children.has(ch)) return false;
return this.search(word, node.children.get(ch), idx + 1);
}
for (const child of node.children.values())
if (this.search(word, child, idx + 1)) return true;
return false;
}
}