Tries (Prefix Trees)

0/12 in this phase0/57 across the roadmap

📖 Concept

A trie (pronounced "try") is a tree structure for storing strings where each node represents a character. It enables O(L) prefix search (L = length of string), independent of how many strings are stored.

Structure:

        root
       / | \
      a   b   c
     / \   \
    p   n   a
   / \   \   \
  p   e   d   t
  |       |
  l       y
  |
  e

Words: apple, ape, and, andy, bat, cat

Operations:

Operation	Complexity
Insert	O(L) — L = word length
Search	O(L)
Prefix search	O(L)
Delete	O(L)

When to use tries:

Autocomplete — find all words with a prefix
Spell checking — is this word in the dictionary?
Word games — Scrabble, Boggle, word search
IP routing — longest prefix matching
DNA/RNA sequence matching

🏠 Real-world analogy: A trie is like a dictionary organized by letter positions. To find "apple", go to 'a' section, then 'ap', then 'app', then 'appl', then 'apple'. Each level narrows the search by one character.

💻 Code Example

codeTap to expand ⛶

1// TRIE NODE
2class TrieNode {
3  constructor() {
4    this.children = {};   // or new Map()
5    this.isEnd = false;   // Marks end of a complete word
6  }
7}
8
9// TRIE — Full Implementation
10class Trie {
11  constructor() { this.root = new TrieNode(); }
12
13  // O(L) — Insert word
14  insert(word) {
15    let node = this.root;
16    for (const char of word) {
17      if (!node.children[char]) {
18        node.children[char] = new TrieNode();
19      }
20      node = node.children[char];
21    }
22    node.isEnd = true;
23  }
24
25  // O(L) — Search exact word
26  search(word) {
27    const node = this._traverse(word);
28    return node !== null && node.isEnd;
29  }
30
31  // O(L) — Check if any word starts with prefix
32  startsWith(prefix) {
33    return this._traverse(prefix) !== null;
34  }
35
36  _traverse(s) {
37    let node = this.root;
38    for (const char of s) {
39      if (!node.children[char]) return null;
40      node = node.children[char];
41    }
42    return node;
43  }
44
45  // Get all words with given prefix
46  autocomplete(prefix) {
47    const node = this._traverse(prefix);
48    if (!node) return [];
49    const results = [];
50    function dfs(node, path) {
51      if (node.isEnd) results.push(path);
52      for (const [char, child] of Object.entries(node.children)) {
53        dfs(child, path + char);
54      }
55    }
56    dfs(node, prefix);
57    return results;
58  }
59}
60
61// TypeScript version
62class TrieNodeTS {
63  children: Map<string, TrieNodeTS> = new Map();
64  isEnd: boolean = false;
65}
66
67class TrieTS {
68  root = new TrieNodeTS();
69
70  insert(word: string): void {
71    let node = this.root;
72    for (const c of word) {
73      if (!node.children.has(c)) node.children.set(c, new TrieNodeTS());
74      node = node.children.get(c)!;
75    }
76    node.isEnd = true;
77  }
78
79  search(word: string): boolean {
80    let node = this.root;
81    for (const c of word) {
82      if (!node.children.has(c)) return false;
83      node = node.children.get(c)!;
84    }
85    return node.isEnd;
86  }
87}
88
89// WORD SEARCH II — Trie + Backtracking
90function findWords(board, words) {
91  const trie = new Trie();
92  for (const w of words) trie.insert(w);
93
94  const result = new Set();
95  const rows = board.length, cols = board[0].length;
96  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
97
98  function dfs(r, c, node, path) {
99    if (node.isEnd) { result.add(path); node.isEnd = false; }
100    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
101    const char = board[r][c];
102    if (!node.children[char]) return;
103    board[r][c] = '#';
104    for (const [dr, dc] of dirs) {
105      dfs(r + dr, c + dc, node.children[char], path + char);
106    }
107    board[r][c] = char;
108  }
109
110  for (let r = 0; r < rows; r++)
111    for (let c = 0; c < cols; c++)
112      dfs(r, c, trie.root, '');
113
114  return [...result];
115}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

Implement a trie with insert, search, and startsWith
Autocomplete — find all words with a given prefix
Word dictionary with wildcard search (. matches any character)
Replace words — replace words in sentence with shortest dictionary root
Longest common prefix using a trie
Word search II — find all dictionary words in a grid
Maximum XOR of two numbers (using binary trie)
Stream of characters — check if suffix forms a word
Palindrome pairs — find pairs whose concatenation is palindrome
Design a search autocomplete system

⚠️ Common Mistakes

Not marking word endings — without isEnd flag, 'app' would match when only 'apple' was inserted
Using array[26] when characters aren't just lowercase letters — use Map for general character sets
Confusing search (exact match) with startsWith (prefix match) — different return conditions
Not implementing delete properly — must check if node has other children before removing
High memory usage with sparse tries — consider compressed tries (radix trees) for memory optimization

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Tries (Prefix Trees)

Was this topic helpful?

← PreviousAdvanced Graph Algorithms (Dijkstra, Topological Sort, Union-Find)Next →Segment Trees — Range Queries & Updates