CODING PATTERNS · LESSON 22 OF 28 · 44 MIN VIDEO · 15 PROBLEMS

Trie

Module Progress (0 / 15 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (44 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Trie — How the Pattern Works

A Trie (Prefix Tree) is a multi-way rooted tree that stores strings or digit sequences one character per edge, maintaining the invariant that every node at depth d uniquely represents the shared d-character prefix of all keys in its subtree. By consolidating shared prefixes onto a single root-to-node path and marking complete words with terminal flags ("$"), a trie answers exact-match and prefix queries in O(L) time proportional only to the query length L rather than dictionary size n—reducing O(n * L) linear scans and O(n log n) comparison sorts. Augmenting nodes with precomputed subtree metadata (such as running sums, earliest indices, shortest-word ties, or lexicographical subtree counts) further turns grid searches, suffix queries, and huge lexicographical rankings into fast prefix walks.

WHEN TO USE THIS PATTERN
  • A dictionary of many strings is queried repeatedly for exact membership, prefix existence (startsWith), longest common prefixes, or shortest root replacements (Replace Words).
  • Characters arrive incrementally or outputs must be produced in lexicographical order—such as typeahead autocomplete (Search Suggestions System), frequency-bucketed alphabetical tie-breaking (Top K Frequent Words), or 1..n dictionary ordering.
  • Multiple words or wildcard patterns are matched simultaneously against a 2D character board (Word Search II), a text string (Index Pairs of a String), or . wildcards, where pruning dead prefixes eliminates exponential branches.
  • Queries compare word suffixes or mirrored concatenations (Longest Common Suffix Queries, Palindrome Pairs), which map directly to prefix walks over a trie of reversed words.
COMMON INTERVIEW PITFALLS
  • Omitting the terminal marker ("$") makes prefixes indistinguishable from complete words, causing search("ca") to falsely return True after inserting "cat".
  • Breaking at the first "$" marker when all matches are required—correct for shortest-root Replace Words, but a bug in Index Pairs of a String and Word Search II where longer words like "aba" or "oat" extend past shorter matches.
  • Iterating child keys without excluding metadata keys (k != "$" or k != "total"), which attempts to traverse a boolean, string, or integer payload as a child dictionary and raises TypeError.
  • Adding raw values instead of net deltas (diff = val - old_val) when updating existing keys in prefix-sum tries (Map Sum Pairs), double-counting the old key value on every ancestor node.
Nested-Dict Trie ConstructionBuilding a compact Python prefix tree over a word list in O(total characters) time using nested dictionaries and a `"$"` terminal marker.
def build_trie(words):
    root = {}
    for word in words:
        cur = root
        for c in word:
            cur = cur.setdefault(c, {})
        cur["$"] = word
    return root
Bounded Lexicographical Subtree DFSCollecting up to `limit` words under a prefix node in ascending alphabetical order (`"$"` sorts before `'a'..'z'`, so shorter words precede extensions).
def collect_sorted(node, limit, out):
    for key in sorted(node):
        if len(out) == limit:
            return out
        if key == "$":
            out.append(node["$"])
        else:
            collect_sorted(node[key], limit, out)
    return out
Wildcard / Pruned Trie BacktrackingMatching patterns with `.` wildcards (or pruning 2D grid searches) by branching only across valid child keys present in the current trie node.
def wildcard_search(node, pattern, i=0):
    if i == len(pattern):
        return "$" in node
    c = pattern[i]
    if c == ".":
        return any(wildcard_search(node[k], pattern, i + 1)
                   for k in node if k != "$")
    return c in node and wildcard_search(node[c], pattern, i + 1)
🔒 PRO PROBLEMTarget: O(total letters) time

11. Longest Common Suffix Queries

Pattern Trigger: shared endings → trie of reversed words

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

The trie holds to, tea and ten. Now we insert top. How many new nodes does that create?