Topic 8: Tries

Canonical Questions #

Trie Implementation & Basic Operations #

This is just about basic trie data structure operations
- Insert, search, and delete words in trie

Problems #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
   class TrieNode:
      def __init__(self):
         self.children = {} # remember it's an edge-check we aren't really interested in storing a collection of nodes.
         self.terminal = False # or we can directly keep the word here to avoid needing to make a root to node walk for the cumulative value.

   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.terminal = True

      def search(self, word):
         node = self._traverse(word)
          return node is not None and node.terminal

      def startsWith(self, prefix):
          return self._traverse(prefix) is not None

      def _traverse(self, string):
         """
          This is a root to node path-walking.
          """
         node = self.root
          for ch in string:
              if ch not in node.children:
                  return None
               node = node.children[ch]
          return node

Code Snippet 1: Implement Trie (208)

Pattern Extraction

Core Insight: A trie stores strings character by character in a tree, where each node has up to 26 children. Insertion/search/prefix check are all \(O(L)\) where \(L\) is the word length. Pattern Name: Prefix Tree (Trie) for String Storage Canonical Section: Tries > Basic Trie Operations Recognition Signals:

“Implement a data structure for storing and searching strings”
Prefix-based operations (startsWith, autocomplete)
Many strings sharing common prefixes

Anti-Signals:

Only exact matching needed (no prefix operations) – hash set is simpler and faster
Binary (bit-level) search – binary trie

Decision Point: Need prefix operations = trie. Only exact matching = hash set. The prefix requirement is the discriminator.

Pitfalls and Misconceptions

Trap: Not distinguishing between a node that is an end-of-word and one that is just a prefix. Why: Without an is_end flag, searching for “app” returns True even if only “apple” was inserted. Correction: Each node has an is_end boolean. Set it to True only at the end of an inserted word.
Trap: Using a list of 26 children when a dictionary would be more flexible. Why: Array of 26 wastes space for sparse tries. Dictionary adapts to actual branching. Correction: self.children = {} for flexibility; self.children = [None] * 26 for performance when alphabet is small and fixed.

Problem Mutations

What if you needed wildcard search (e.g., d.. matches “dog”)? (stress-tests: exact matching) At each wildcard position, recurse into ALL children. Connects to LC 211 Add and Search Word.
What if you needed autocomplete (return all words with a given prefix)? (stress-tests: boolean prefix check) Navigate to the prefix node, then DFS to collect all complete words.
What if you needed the longest common prefix of all inserted words? (stress-tests: per-word operations) Navigate down the trie until a node has more than one child or is an end-of-word. Connects to LC 14.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Implement Trie generated via batch canonical enrichment pass.

Wildcard Matching / Add & Search Word #

In general, this will affect how we do searching but the same prefix tree is what gets used.
Search with wildcards (’.’) and pattern matching

Problems #

Add & Search Word (211)

We can see this as a DFS with wildcard matching helping us out for the candidate selection. It’s not that complicated if we calm down about it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   from collections import defaultdict

    class WordDictionary:
        def __init__(self):
            self.root = defaultdict(dict)
            self.terminal = "#"

        def addWord(self, word: str) -> None:
            node = self.root
            for ch in word:
                if ch not in node:
                    node[ch] = defaultdict(dict)
                    node = node[ch]
                    node[self.terminal] = True

        def search(self, word: str) -> bool:
            def dfs(i, node):
                if i == len(word):
                    return self.terminal in node
                ch = word[i]
                if ch == ".":
                    return any(
                        dfs(i + 1, next_node) for key, next_node in node.items() if key != self.terminal
                    )
                if ch not in node:
                    return False

                return dfs(i + 1, node[ch])

            return dfs(0, self.root)

Code Snippet 2: Add & Search Word (211) – DFS approach

Alternatively, I had this approach, though I think the DFS approach is better because there’s no need to declare a custom TrieNode class of our own here.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
    class Node:
        def __init__(self, val=None, terminal=False):
            self.children = dict()
            self.val = val
            self.terminal = terminal

    class WordDictionary:
        def __init__(self):
            self.root = Node()
            self.wild = "."

        def addWord(self, word: str) -> None:
            ptr = self.root
            for char in word:
                if char not in ptr.children:
                    ptr.children[char] = Node(val=char)
                    ptr = ptr.children[char]
                    # terminate:
            ptr.terminal = True

            return
    def search(self, word: str) -> bool:
        options = [self.root]

        for idx, char in enumerate(word):
            next_options = []

            for node in options:
                if char == self.wild:
                    # Try all possible children
                    next_options.extend(node.children.values())
                else:
                    if char in node.children:
                        next_options.append(node.children[char])

            # No valid paths
            if not next_options:
                return False

            options = next_options

        # After processing all characters, check terminal flag
        return any(node.terminal for node in options)

Pattern Extraction

Core Insight: Standard trie with wildcard support. For exact characters, follow the single trie path. For . (wildcard), recurse into ALL children at that position. Pattern Name: Trie with Wildcard DFS Canonical Section: Tries > Wildcard Matching Recognition Signals:

“Search with wildcards” in a dictionary
. matches any single character
Exact match for non-wildcard characters

Anti-Signals:

No wildcards – standard trie search
* (match zero or more) – more complex, regex matching

Decision Point: Single-character wildcard = DFS into all children at wildcard positions. Multi-character wildcard = DP or NFA-based approach.

Pitfalls and Misconceptions

Trap: Using a hash set instead of a trie. Why: Hash sets don’t support efficient wildcard search. You’d have to check all words. Correction: Trie enables character-by-character traversal with branching at wildcards.
Trap: Not exploring ALL children when a . is encountered. Why: . matches any character. Must recurse into every non-null child. Correction: for child in node.children.values(): if dfs(child, i+1): return True.

Problem Mutations

What if wildcards could match zero or more characters? (stress-tests: single character wildcard) Much harder. Connects to regex matching (LC 10) or wildcard matching (LC 44).
What if deletions were also supported? (stress-tests: insert and search only) Trie deletion: decrement reference counts along the path, remove nodes with zero references.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Add &amp; Search Word.

TODO Implement Magic Dictionary (676)

Multiword Search (Word Search with Trie) #

here the objective is to use a try for a better representation of the search space. We can use tries as supporting, aux datastructures to optimise other problems.
In these cases, we should remember to consider “turning off” a terminal node once found to avoid infinite recursion / double counting cases.
- Use trie to speed up multiple word searches in 2D grids

Problems #

Word Search II (212)

This requires us to find so many words, we want to prune our actions by realising that we can avoid the repeated searches for the common prefixes over and over. So instead of a list, we preprocess as a trie and direct our efforts better. The rest is just DFS, guided by the existence in the trie.

We also see another optimisation where we can “prune the trie” after finding out a word, we need to effectively off it so that we don’t double count it again.

Also, we can ignore more dead-ends by removing the node if the child has no children.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
   from collections import defaultdict

   class Node:
      def __init__(self):
         self.children = defaultdict(Node)
         self.word = None

   class Solution:
      def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
         ROWS, COLS = len(board), len(board[0])
         DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
         VISITED = "*"

          res = []

          # we build the trie:
          root = Node()
          for w in words:
             ptr = root
              for c in w:
                 ptr = ptr.children[c]
                 ptr.word = w

          def backtrack(r, c, node): # this is more of a DFS rather than "backtracking"
             cell = board[r][c]

              if cell not in node.children:
                  return

              child = node.children[cell]
              if child.word:
                 res.append(child.word)
                 child.word = None # set it off

                  # OPTIMISATION: remove if the child has no children, which prunes dead-ends:
                  if not child.children:
                     node.children.pop(cell)

              board[r][c] = VISITED

              for row, col in ((r + dr, c + dc) for dr, dc in DIRS if  (
                    0 <= r + dr < ROWS and 0 <= c + dc < COLS and board[r + dr][c + dc] != VISITED
              )):
                 # choose it:
                  backtrack(row, col, child)

              board[r][c] = cell

              return

          for row, col in ((r, c) for r in range(ROWS) for c in range(COLS)):
             backtrack(row, col, root)

          return res

Code Snippet 3: Word Search II (212)

Pattern Extraction

Core Insight: Build a trie from the word list. DFS on the grid, following trie paths. This avoids redundant DFS restarts for words sharing prefixes. Pattern Name: Trie-Guided Grid DFS Canonical Section: Tries > Multi-Pattern Grid Search Recognition Signals:

“Find all words from a dictionary in a grid”
Multiple words to search (not just one – that’s LC 79)
Words share prefixes (trie exploits this)

Anti-Signals:

Only one word to search – simple DFS/backtracking without trie. LC 79
Grid is very large but word list is small – per-word DFS might be acceptable

Decision Point: Single word search = backtracking DFS (LC 79). Multiple word search = trie + backtracking DFS (LC 212). The trie amortises the cost of shared prefixes.

Pitfalls and Misconceptions

Trap: Running a separate DFS for each word (ignoring the trie). Why: \(O(k \cdot m \cdot n \cdot 4^L)\) where \(k\) is the number of words. The trie approach shares work across words with common prefixes. Correction: Build a trie from all words. During grid DFS, follow the trie – if a trie path doesn’t exist for the current character, prune.
Trap: Not pruning trie nodes after finding a word. Why: Without pruning, the DFS continues to search for already-found words, wasting time. Correction: After finding a word, remove the leaf node (and parent nodes with no other children) to avoid redundant searches.
Trap: Not marking grid cells as visited during the current DFS path. Why: Without visited marking, the DFS can revisit cells in the current path, forming invalid words. Correction: Temporarily mark board[r][c] = '#' during DFS, restore after backtracking.

Problem Mutations

What if the dictionary were dynamic (words added/removed between queries)? (stress-tests: static dictionary) Rebuild the trie on changes, or maintain it incrementally. Trie supports efficient insertion and deletion.
What if the grid could wrap around (toroidal)? (stress-tests: bounded grid) Use modular arithmetic for neighbours. Trie approach is unchanged.
What if you needed to find the LONGEST word from the dictionary in the grid? (stress-tests: all words) Trie-guided DFS but track the longest match. Don’t stop at the first found word.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Word Search II generated via batch canonical enrichment pass.

TODO Replace Words (648)

Autocomplete & Prefix Counting #

Count words with given prefix, autocomplete suggestions (extension)

Problems #

Prefix counting and autocomplete implementations
TODO Search suggestion systems (1268)
TODO Design Search Autocomplete System (642) (paid qns)

Longest Common Prefix & Suffix Queries #

Use tries (possibly reversed) to find longest common prefixes or suffixes among a set of strings efficiently.

Problems #

Longest Common Prefix (classic variations)

Longest Common Prefix (14)

My first-reach solution was to do a try-except as part of the main logic flow, which is kind of unideal.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
      class Solution:
          def longestCommonPrefix(self, strs: List[str]) -> str:
              if any(not s for s in strs):
                  return ""

              idx = 0
              while True:
                  try:
                      if len(set(s[idx] for s in strs)) == 1:
                          idx += 1
                      else:
                          return strs[0][:idx]

                  except:
                      return strs[0][:idx]

Code Snippet 4: Longest Common Prefix (14)

Should try not to use try-excepts as part of the primary logic.

In this case, we could have implemented a vertical scanning approach like so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
      class Solution:
          def longestCommonPrefix(self, strs: List[str]) -> str:
              if not strs:
                  return ""
              for i in range(len(strs[0])):
                  char = strs[0][i]
                  for s in strs[1:]:
                      if i == len(s) or s[i] != char:
                          return strs[0][:i]
              return strs[0]

Code Snippet 5: Longest Common Prefix (14)

As trie-based solution is a little overkill, but here’s the solution for didactic purposes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
      class TrieNode:
          def __init__(self):
              self.children = {}
              self.is_end_of_word = False

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

          def insert(self, word):
              node = self.root
              for char in word:
                  if char not in node.children:
                      node.children[char] = TrieNode()
                      node = node.children[char]
                      node.is_end_of_word = True

          def longest_common_prefix(self):
              prefix = []
              node = self.root
              # Traverse while node has exactly one child and is not end of word
              while node and not node.is_end_of_word and len(node.children) == 1:
                  char = next(iter(node.children))  # get the single child key
                  prefix.append(char)
                  node = node.children[char]
              return "".join(prefix)


      class Solution:
          def longestCommonPrefix(self, strs: list[str]) -> str:
              if not strs:
                  return ""
              trie = Trie()
              for word in strs:
                  if word == "":
                      return ""
                  trie.insert(word)
              return trie.longest_common_prefix()

Code Snippet 6: Longest Common Prefix (14) – A trie based solution (overkill)

Pattern Extraction

Core Insight: Compare characters position by position across all strings. Stop when any string ends or a mismatch is found. Alternatively, use a trie: the LCP is the path from root until a node has more than one child or is end-of-word. Pattern Name: Vertical Scanning / Trie-Based LCP Canonical Section: Tries > Prefix Operations Recognition Signals:

“Longest common prefix” of an array of strings
Character-by-character comparison
Short-circuit on first mismatch

Anti-Signals:

Longest common SUBSTRING (not prefix) – different problem, use suffix array or DP
LCP between exactly two strings – even simpler, single scan

Decision Point: Vertical scanning (\(O(S)\) where \(S\) = total characters) is simplest. Trie approach is overbuilt unless you need to support dynamic insertions and prefix queries.

Pitfalls and Misconceptions

Trap: Sorting the strings and comparing only the first and last. Why: Works (LCP of sorted first and last is the overall LCP) but is \(O(S \log n)\) due to sorting. Vertical scan is \(O(S)\). Correction: Vertical scan is simpler and faster. But the sort trick is a valid interview shortcut.
Trap: Not handling the empty array or empty string cases. Why: Edge cases: empty array returns '', array with one string returns that string. Correction: Early return for edge cases.

Problem Mutations

What if strings were added dynamically and you needed LCP queries? (stress-tests: static array) Build a trie. LCP = depth of the longest single-child path from root.
What if you needed the LCP of two specific strings in the array? (stress-tests: all strings) Sort + LCP array (suffix array technique) for \(O(1)\) per query after \(O(S \log n)\) preprocessing.

AI usage disclosure Claude Opus 4.6 · content enrichment

    Batch annotation for Longest Common Prefix.

TODO short encoding of words (820) Shortest Unique Prefix for every word 820
TODO longest word in dictionary (720)

Distinct Substrings / Subsequence Count #

Use tries (or suffix tries/trees) to count distinct substrings or perform substring query-related tasks.

Problems #

Count distinct substrings of a string
Number of different sub-strings (variations in suffix trie)

IP Routing / Prefix Matching (Specialized Tries) #

Tries are used to implement longest prefix matching in networking (e.g., Routing tables).

Problems #

Not common on Leetcode, but classic applications in system design.

Compression & Dictionary Encoding #

Tries can be used for compression tasks like dictionary compression or encoding sets of strings.

Problems #

Remove Duplicate Letters (lex order variant that uses trie conceptually)
Optimal prefix codes (Huffman coding, conceptually related)
TODO String Compression (443)

⭐️ Bitwise or Binary Tries (for Integers) #

Binary tries store integers bitwise to answer max XOR queries, or minimum/maximum XOR computations.

Problems #

TODO Maximum XOR of Two Numbers in an Array (421)
TODO HARD Maximum XOR With an Element From Array (1707)

Dynamic Updates & Modification in Trie #

Insertions and deletions in dynamic sets of strings with efficient query support.

Problems #

Online dictionary updates with prefix queries
Implement data structure supporting add and remove of strings with prefix queries

SOE #

Mental Model issues:
1. seeing tries as a collection of children nodes instead of a map of maps that holds edges (correct)
Implementation:
1. NOT making the most out of using map of maps for this \(\implies\) easiest to just use nested maps here
2. Forgetting to mark end-of-word in nodes
Overusing memory leading to blowup (high branching factor)
Poor handling of edge cases such as empty strings or duplicate inserts

Trie Construction #

Forgetting to mark the end of a word (node.is_end = True): search will find prefixes but not complete words.
Using a single Trie for both insert and search when the problem requires separate prefix and word-completion semantics.

Trie Search #

In wildcard search (e.g., “.” matching), forgetting to recurse into ALL children at the wildcard position, not just the first match.
Confusion between search (exact word match, requires is_end) and startsWith (prefix match, does NOT require is_end).

AI usage disclosure Claude Opus 4.6 · content enrichment

SOE entries synthesised from common Trie implementation mistakes. Review and adjust.

Decision Flow #

Need prefix query or inserts? → Trie basic operations
Wildcard or pattern search? → DFS combined with trie
Multiple word queries over grids? → Trie + backtracking
Large dictionaries? → Optimize with compressed tries or suffix trees

Styles, Tricks and Boilerplate #

Styles #

I prefer using a dict instead of children array for this, the key itself can be the edge label and the value can be the TrieNode.
encode the terminus correctly, a flag or the actual work works well. If actual word, we can just get it directly without having to do the whole root to node walk.

Trick #

for tries being used as a input space, remember to prune when necessary e.g. in the Word Search II problem.

Boilerplate #

Classic trie implementation. Remember that it’s going to end up

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 class TrieNode:
     def __init__(self):
         self.children = {}
         self.terminal = False # or we can directly keep the word here

 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.terminal = True

     def search(self, word):
         node = self._traverse(word)
         return node is not None and node.terminal

     def startsWith(self, prefix):
         return self._traverse(prefix) is not None

     def _traverse(self, string):
         node = self.root
         for ch in string:
             if ch not in node.children:
                 return None
             node = node.children[ch]
         return node

Code Snippet 7: Trick

Also realise that if we don’t need to have a dedicated class for this, we could have chosen to just use a deeply-nested dictionary for this instead of a dedicate TrieNode class.

TODO KIV #

Existing Canonicals #

Technique	Problem	LeetCode	Status
binary tries	Maximum XOR of Two Numbers in an Array	421	TODO
binary tries	Maximum XOR With an Element From Array	1707	TODO, HARD
dynamic modification in trie	Online Stock Span	901	TODO
wildcard matching	Implement Magic Dictionary	676	TODO
longest common prefix/suffix queries	Short Encoding of Words	820	TODO
Multiword Search	Replace Words	648	TODO
autocomplete/prefix counting	Search Suggestion Systems	1268	TODO
autocomplete	Design Search Autocomplete System	642	TODO
compression & dictionary encoding	String Compression	443	TODO