Algorithms & Coding Interviews · Recursion & Trees

Tries

A trie stores strings by shared prefixes, so insert and lookup cost O(word length) no matter how many words are stored. Learn the node structure, when a trie beats a hash set, the common extensions (counts, autocomplete, wildcards, grid search), and watch words being inserted and searched step by step.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 12 min read▶ 2 interactive🛠️ 4 exercises

🎯 What you'll learn

Trie nodes, end flags and O(L) operations
When tries beat hash sets
Prefix counts, autocomplete, wildcards and Word Search II
Six LeetCode problems with an animated trie

📚 Before you start

Part 1The Pattern

A trie (prefix tree) stores strings character by character: each edge is a character, each path from the root spells a prefix, and a flag marks where complete words end. Inserting or looking up a word costs O(L) for its length L, independent of how many words are stored, and every word sharing a prefix shares the same path. That makes tries the natural answer to prefix queries: autocomplete, "starts with", wildcard search, and searching many words at once in a grid.

A trie holding app, apple, apt and bat; shared prefixes share nodes

1When to Use a Trie

Need	Trie	Hash set
exact membership	O(L)	O(L) to hash, simpler
"any word starts with p?" / all words with prefix p	O(L + matches)	must scan every word
wildcard (`b.d`)	DFS over children	scan everything
search many dictionary words in a grid	one DFS, prune dead prefixes	one search per word
longest common prefix / shortest unique prefix	walk while one child	awkward

2Template

typescript

class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TrieNode());
      node = node.children.get(c)!;
    }
    node.isEnd = true;
  }
  private walk(s: string): TrieNode | null {
    let node: TrieNode | undefined = this.root;
    for (const c of s) {
      node = node.children.get(c);
      if (!node) return null;
    }
    return node;
  }
  search(word: string): boolean { const n = this.walk(word); return n !== null && n.isEnd; }
  startsWith(prefix: string): boolean { return this.walk(prefix) !== null; }
}

function trieDemo(words: string[], queries: string[]): boolean[][] {
  const t = new Trie();
  for (const w of words) t.insert(w);
  return queries.map((q) => [t.search(q), t.startsWith(q)]);
}

python

class TrieNode:
    def __init__(self):
        self.children = {}          # char -> TrieNode
        self.is_end = False         # a word ends here

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def _walk(self, s):
        node = self.root
        for c in s:
            node = node.children.get(c)
            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

def trie_demo(words, queries):
    t = Trie()
    for w in words:
        t.insert(w)
    return [[t.search(q), t.starts_with(q)] for q in queries]

Children can be a hash map (any alphabet, memory-light for sparse nodes) or a fixed array of 26 (faster, lowercase only). Mention the trade-off.

3Common Extensions

Count prefixes: store count on each node (words passing through) for "how many words start with p".
Autocomplete: walk to the prefix node, then DFS to collect words (store up to 3 best suggestions per node for speed, as in Search Suggestions System).
Wildcards: on ., try every child recursively.
Word Search II: build a trie of the dictionary, DFS the grid along trie edges, and prune any trie branch once its words are found.

Under the HoodMemory and Radix Trees▾

A naive trie can use a lot of memory: one node per character with a children map. Production systems compress chains of single-child nodes into one edge labelled with a whole substring: a radix tree (Patricia trie). Linux's routing tables use them for IP prefix lookup, Redis uses a radix tree for Streams and cluster slot mapping, and HTTP routers (Go's httprouter, Fastify's find-my-way) use them to match URL paths. Search engines' autocomplete layers use tries or FSTs (finite-state transducers) that also share suffixes.

⚠️ Common Pitfalls

Forgetting the end-of-word flag: after inserting "apple", "app" must not count as a word unless inserted.
Confusing search and startsWith: both walk the path; only search checks the flag.
Rebuilding the trie per query instead of once.
Not pruning in Word Search II: without removing found words, the search revisits dead branches.
Memory blow-up with 26-slot arrays on sparse data.

📋 Quick Reference

text

insert: node = root; for c: node = node.children.setdefault(c, Node()); node.end = True
search: walk; return node and node.end · startsWith: walk; return node is not None
O(L) per operation · space O(total characters)

Part 2Interview Problems

Six problems: implementing the trie, wildcard search, grid search over many words, prefix replacement and autocomplete.

1Implement Trie (Prefix Tree) (LeetCode 208)

🟠 Medium. Implement insert(word), search(word) and startsWith(prefix).

text

insert("apple"), search("apple") → true, search("app") → false, startsWith("app") → true

Approach. Nodes with a children map and an end flag. insert creates missing nodes along the path and marks the end; search and startsWith walk the path, and only search checks the end flag.

Complexity. O(L) per operation; space O(total characters inserted).

typescript

class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TrieNode());
      node = node.children.get(c)!;
    }
    node.isEnd = true;
  }
  private walk(s: string): TrieNode | null {
    let node: TrieNode = this.root;
    for (const c of s) {
      const next = node.children.get(c);
      if (!next) return null;
      node = next;
    }
    return node;
  }
  search(word: string): boolean { const n = this.walk(word); return !!n && n.isEnd; }
  startsWith(prefix: string): boolean { return this.walk(prefix) !== null; }
}

python

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 c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def _walk(self, s):
        node = self.root
        for c in s:
            if c not in node.children:
                return None
            node = node.children[c]
        return node

    def search(self, word):
        node = self._walk(word)
        return bool(node and node.is_end)

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

2Design Add and Search Words Data Structure (LeetCode 211)

🟠 Medium. Support addWord(word) and search(pattern) where . matches any single letter.

text

addWord bad, dad, mad · search("pad") → false · search(".ad") → true · search("b..") → true

Approach. Trie plus DFS: for a normal character follow that child; for ., try every child. Return true if any branch reaches the end of the pattern on an end-of-word node.

Complexity. O(L) to add; search is O(L) without dots and up to O(26ᴸ) in the worst case with many dots.

typescript

class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class WordDictionary {
  private root = new TrieNode();
  addWord(word: string): void {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TrieNode());
      node = node.children.get(c)!;
    }
    node.isEnd = true;
  }
  search(word: string): boolean {
    const dfs = (node: TrieNode, i: number): boolean => {
      if (i === word.length) return node.isEnd;
      const c = word[i];
      if (c === ".") {
        for (const child of node.children.values()) if (dfs(child, i + 1)) return true;
        return false;
      }
      const next = node.children.get(c);
      return !!next && dfs(next, i + 1);
    };
    return dfs(this.root, 0);
  }
}

python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def add_word(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def search(self, word):
        def dfs(node, i):
            if i == len(word):
                return node.is_end
            c = word[i]
            if c == ".":
                return any(dfs(child, i + 1) for child in node.children.values())
            return c in node.children and dfs(node.children[c], i + 1)
        return dfs(self.root, 0)

3Word Search II (LeetCode 212)

🔴 Hard. Return all dictionary words that can be traced on the letter grid (adjacent cells, each used once per word).

text

board 4×4, words ["oath","pea","eat","rain"] → ["eat","oath"]

Approach. Build a trie of the words (store the full word at its end node). DFS from every cell, moving only along trie edges, so dead prefixes are abandoned immediately. When a node with a word is reached, record it and clear it (no duplicates); remove exhausted leaves to prune future searches.

Complexity. O(R · C · 4 · 3ᴸ⁻¹) in the worst case, but pruning makes it fast in practice; trie space O(total letters).

typescript

type Node = { kids: Map<string, Node>; word: string | null };

function findWords(board: string[][], words: string[]): string[] {
  const root: Node = { kids: new Map(), word: null };
  for (const w of words) {
    let node = root;
    for (const c of w) {
      if (!node.kids.has(c)) node.kids.set(c, { kids: new Map(), word: null });
      node = node.kids.get(c)!;
    }
    node.word = w;
  }
  const R = board.length, C = board[0].length, found: string[] = [];
  const dfs = (r: number, c: number, parent: Node): void => {
    const ch = board[r][c], node = parent.kids.get(ch)!;
    if (node.word) { found.push(node.word); node.word = null; }
    board[r][c] = "#";
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < R && nc < C && node.kids.has(board[nr][nc])) dfs(nr, nc, node);
    }
    board[r][c] = ch;
    if (node.kids.size === 0 && !node.word) parent.kids.delete(ch);
  };
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (root.kids.has(board[r][c])) dfs(r, c, root);
  return found;
}

python

def find_words(board, words):
    root = {}
    for w in words:
        node = root
        for c in w:
            node = node.setdefault(c, {})
        node["$"] = w                                  # word stored at its end
    R, C, found = len(board), len(board[0]), []

    def dfs(r, c, parent):
        ch = board[r][c]
        node = parent[ch]
        if "$" in node:
            found.append(node.pop("$"))                # record once
        board[r][c] = "#"
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and board[nr][nc] in node:
                dfs(nr, nc, node)
        board[r][c] = ch
        if not node:
            parent.pop(ch)                             # prune an exhausted branch

    for r in range(R):
        for c in range(C):
            if board[r][c] in root:
                dfs(r, c, root)
    return found

4Longest Common Prefix (LeetCode 14)

🟢 Easy. Return the longest common prefix of an array of strings.

text

["flower","flow","flight"] → "fl"

Approach. Vertical scan: compare character i of every string until one differs or a string ends. (With a trie: insert all words and walk down while the node has exactly one child and isn't a word end. Useful when the set changes or queries repeat.)

Complexity. O(S) time for S total characters, O(1) extra space.

typescript

function longestCommonPrefix(strs: string[]): string {
  if (!strs.length) return "";
  for (let i = 0; i < strs[0].length; i++) {
    for (const s of strs) if (i === s.length || s[i] !== strs[0][i]) return strs[0].slice(0, i);
  }
  return strs[0];
}

python

def longest_common_prefix(strs):
    if not strs:
        return ""
    for i, ch in enumerate(strs[0]):
        for s in strs[1:]:
            if i == len(s) or s[i] != ch:
                return strs[0][:i]
    return strs[0]

5Replace Words (LeetCode 648)

🟠 Medium. Replace every word in sentence by the shortest dictionary root that is its prefix (if any).

text

roots ["cat","bat","rat"], "the cattle was rattled by the battery" → "the cat was rat by the bat"

Approach. Insert roots into a trie. For each word, walk the trie character by character and stop at the first end-of-root node; that prefix is the replacement. If the walk falls off the trie first, keep the word.

Complexity. O(total characters) time.

typescript

function replaceWords(dictionary: string[], sentence: string): string {
  type N = { [k: string]: N } & { $?: boolean };
  const root: N = {} as N;
  for (const w of dictionary) {
    let node = root;
    for (const c of w) node = (node[c] ??= {} as N);
    node.$ = true;
  }
  const shortest = (word: string): string => {
    let node = root;
    for (let i = 0; i < word.length; i++) {
      node = node[word[i]];
      if (!node) return word;
      if (node.$) return word.slice(0, i + 1);
    }
    return word;
  };
  return sentence.split(" ").map(shortest).join(" ");
}

python

def replace_words(dictionary, sentence):
    root = {}
    for w in dictionary:
        node = root
        for c in w:
            node = node.setdefault(c, {})
        node["$"] = True

    def shortest_root(word):
        node = root
        for i, c in enumerate(word):
            if c not in node:
                return word
            node = node[c]
            if "$" in node:
                return word[:i + 1]
        return word

    return " ".join(shortest_root(w) for w in sentence.split())

6Search Suggestions System (LeetCode 1268)

🟠 Medium. After each typed character of searchWord, return up to three lexicographically smallest products starting with the typed prefix.

text

products [mobile, mouse, moneypot, monitor, mousepad], "mouse" → [[mobile,moneypot,monitor], …, [mouse,mousepad]]

Approach. Sort the products, insert them into a trie, and store at each node the first three products passing through it (sorted insertion makes them the smallest). Then walk the trie with the typed characters; once the walk falls off, every remaining prefix has no suggestions. (A sort + binary search solution is equally good.)

Complexity. O(S log S) to sort plus O(total characters) to build; O(L) to answer.

typescript

function suggestedProducts(products: string[], searchWord: string): string[][] {
  type N = { kids: Map<string, N>; top: string[] };
  const root: N = { kids: new Map(), top: [] };
  for (const p of [...products].sort()) {
    let node = root;
    for (const c of p) {
      if (!node.kids.has(c)) node.kids.set(c, { kids: new Map(), top: [] });
      node = node.kids.get(c)!;
      if (node.top.length < 3) node.top.push(p);
    }
  }
  const res: string[][] = [];
  let node: N | undefined = root;
  for (const c of searchWord) {
    node = node?.kids.get(c);
    res.push(node ? node.top : []);
  }
  return res;
}

python

def suggested_products(products, search_word):
    root = {}
    for p in sorted(products):
        node = root
        for c in p:
            node = node.setdefault(c, {"#": []})
            if len(node["#"]) < 3:
                node["#"].append(p)
    res, node = [], root
    for c in search_word:
        node = node.get(c) if node else None
        res.append(node["#"] if node else [])
    return res

🧠 Key takeaways

A trie shares prefixes: O(L) insert/search, independent of how many words are stored.
search checks the end flag; startsWith only needs the path.
Extensions: prefix counts, top-3 suggestions per node, . wildcards via DFS.
Word Search II: trie + grid DFS, prune found words and empty branches.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_tries_exercise_1.py

TS PY

algo_tries_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. After inserting only 'apple', search('app') returns…

No end flag at 'app'.

2. Why does a trie beat a hash set for 'all words starting with pre'?

Prefix sharing.

3. Insert/search cost in a trie is…

One node per character.

4. A radix tree improves a trie by…

Less memory.

Source: algo_tries_theory_1.md, algo_tries_theory_2.md · generated by tools/build_lessons.py