Trie (Prefix Tree): Code Templates in 6 Languages
If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview. Every operation here runs in
Main Template: The Standard Trie
This is the core trie with insert, search, startsWith, and delete. It directly solves Implement Trie (Prefix Tree) , and the delete method covers the follow-up interviewers often ask about that LeetCode problem does not include.
class TrieNode {
constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
// The last node of the word carries the end marker,
// which is what separates search from startsWith later.
node.isEndOfWord = true;
}
search(word) {
const node = this._getNode(word);
return node !== null && node.isEndOfWord;
}
startsWith(prefix) {
return this._getNode(prefix) !== null;
}
delete(word) {
return this._deleteHelper(this.root, word, 0);
}
_getNode(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
return null;
}
node = node.children.get(char);
}
return node;
}
_deleteHelper(node, word, index) {
if (index === word.length) {
// Only a stored word can be deleted, not a bare prefix.
if (!node.isEndOfWord) return false;
node.isEndOfWord = false;
// The node itself survives only if words continue below it.
return node.children.size === 0;
}
const char = word[index];
if (!node.children.has(char)) return false;
const shouldPrune = this._deleteHelper(node.children.get(char), word, index + 1);
if (shouldPrune) {
node.children.delete(char);
// Stop pruning upward once a node is still a word end
// or still has other children, because they are in use.
return node.children.size === 0 && !node.isEndOfWord;
}
return false;
}
}Code Breakdown
Key Variables
root: the entry node, which represents the empty prefix. Every word starts its descent here, and the node itself never carries a character.children: the map from character to child node. The map version accepts any alphabet without pre-allocating space.isEndOfWord: the marker that records whether a complete word ends at this node. It is the single line that separates search from startsWith.
Visual Mechanism
Insert and search share one descent loop. The only difference is what happens when a character is missing.
flowchart TD
Start["Start at root"] --> Child{"Next character is a child?"}
Child -->|"No"| Create["Create the node"]
Create --> Move["Move to the node"]
Child -->|"Yes"| Move
Move --> More{"More characters left?"}
More -->|"Yes"| Child
More -->|"No"| Mark["Mark the node as a word end"]
flowchart TD
Start["Start at root"] --> Child{"Next character is a child?"}
Child -->|"No"| False["Return false"]
Child -->|"Yes"| Move["Move to the child node"]
Move --> More{"More characters left?"}
More -->|"Yes"| Child
More -->|"No"| End{"Current node is a word end?"}
End -->|"Yes"| True["Return true"]
End -->|"No"| False
Critical Sections
The descent loop is the whole structure. Insert creates a node when the character is missing, moves down, and repeats. Search does the same walk but gives up the moment a character is absent. Both loops run exactly M steps, which is where the
The end marker sits at the end of insert and inside search’s final check. Skipping it in search is the classic bug, because search would then return true for any stored prefix.
Delete is the only operation that needs recursion. It descends to the final node, unsets the marker, and reports upward whether the node can be pruned. A node is prunable only when it has no children and is not itself the end of another word. The boolean return value carries that decision up one level at a time, so the recursion removes exactly the nodes that became dead, nothing more.
Variations
1. Wildcard Search
Use this when the search string may contain a wildcard character, usually “.”, that matches any single character. This variation solves Design Add and Search Words Data Structure
. It reuses the TrieNode class from the main template.
Complexity: add runs in
class WordDictionary {
constructor() {
this.root = new TrieNode();
}
addWord(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
}
search(word) {
return this._dfs(word, 0, this.root);
}
_dfs(word, index, node) {
if (index === word.length) {
return node.isEndOfWord;
}
const char = word[index];
if (char === '.') {
// A wildcard can match any character, so every child
// branch is a candidate and one success is enough.
for (const child of node.children.values()) {
if (this._dfs(word, index + 1, child)) {
return true;
}
}
return false;
}
if (!node.children.has(char)) {
return false;
}
return this._dfs(word, index + 1, node.children.get(char));
}
}2. Array-Backed Trie for a Fixed Alphabet
Use this when the alphabet is small and known up front, like 26 lowercase letters or 4 DNA bases. A fixed array of child slots removes the map lookup, but every node allocates its full array even when most slots stay empty. Same
// For lowercase letters only, children can be a fixed array of 26 slots.
// The character code minus 97 maps a..z to indices 0..25.
class ArrayTrieNode {
constructor() {
this.children = new Array(26).fill(null);
this.isEndOfWord = false;
}
}
class ArrayTrie {
constructor() {
this.root = new ArrayTrieNode();
}
_index(char) {
return char.charCodeAt(0) - 97;
}
insert(word) {
let node = this.root;
for (const char of word) {
const idx = this._index(char);
if (!node.children[idx]) {
node.children[idx] = new ArrayTrieNode();
}
node = node.children[idx];
}
node.isEndOfWord = true;
}
search(word) {
let node = this.root;
for (const char of word) {
const idx = this._index(char);
if (!node.children[idx]) return false;
node = node.children[idx];
}
return node.isEndOfWord;
}
}3. Prefix Enumeration (Autocomplete)
Use this when the problem asks to list every stored word that starts with a given prefix. The prefix walk finds the node, then a depth-first traversal of the subtree collects every word below it. It reuses the TrieNode class from the main template. Enumerating all N stored words costs
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
}
getWordsWithPrefix(prefix) {
const node = this._getNode(prefix);
if (!node) return [];
const results = [];
this._collect(node, prefix, results);
return results;
}
_getNode(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
return null;
}
node = node.children.get(char);
}
return node;
}
_collect(node, current, results) {
// Every end marker below this node is one complete word,
// and the path to it is that word.
if (node.isEndOfWord) {
results.push(current);
}
for (const [char, child] of node.children) {
this._collect(child, current + char, results);
}
}
}Now head to the practice problems to apply these templates to real interview questions.