Skip to content

Volume ITechnology

4.15.0 — Tries: The Pattern ​

Recognition cue. The problem says prefix, starts with, dictionary, autocomplete, or asks you to match many words at once.

The move. A tree where each edge is a character, so words sharing a prefix share the nodes for it. Lookup costs O(L) for a key of length L, independent of how many keys are stored.

The structure ​

python
class TrieNode:
    def __init__(self):
        self.children = {}      # character → TrieNode
        self.is_word = False    # or: self.word = None, storing the whole word
python
# insert
node = root  # (1)
for c in word:  # (2)
    node = node.children.setdefault(c, TrieNode())  # (3)
node.is_word = True  # (4)

# walk (shared by search and startsWith)
node = root  # (5)
for c in prefix:
    if c not in node.children: return None  # (6)
    node = node.children[c]  # (7)
return node  # (8)

The template, line by line.

(1) Every walk starts at the root, which stands for the empty prefix. (2) Take the word one character at a time. (3) Step to the child for this character, creating it first if it is missing. setdefault(c, TrieNode()) does both in one call. (4) Mark that a whole word ends at this node.

(5) The shared walk also starts at the root. (6) If a character has no child, no stored word starts with this prefix, so stop. (7) Otherwise step down. (8) Return the node the prefix ends on. search then checks its flag, and startsWith only checks that it exists.

search checks the flag on the node it lands on. startsWith does not. Those two differ by exactly one line, and that difference is what the flag exists for.

Trie or hash set? ​

triehash set
exact lookupO(L)O(L) to hash, then O(1)
prefix queriesO(L)impossible without scanning everything
sorted iterationfreeneeds a sort
memoryshares prefixesstores every key whole

Use a trie only when prefixes matter. For plain membership, a set is simpler and faster.

The three problems ​

#ProblemThe one insight
4.15.1Implement Trie ★The is_word flag separates a word from a prefix
4.15.2Add and Search Words ★A wildcard turns the walk into a branching DFS
4.15.3Word Search II ★The trie prunes the grid search after one wrong letter

★ marks the Blind 75 subset.

The traps on this pattern ​

Forgetting the word-end flag. Without it you cannot tell "ca" from "cat", and search becomes startsWith.

Returning True instead of the flag at the end of a search. A path existing is not the same as a word ending there.

Allocating 26 slots per node when the data is sparse. A map costs less and handles any alphabet; an array is faster on dense lowercase data. Say which trade you took.

Forgetting the undo in Word Search II. The board cell must be restored, or later searches find nothing.

Returning early after a match in Word Search II. A longer word may continue through the same cell.

What the interviewer will push on ​

"Why not a hash set?" No prefix queries.

"What is the complexity?" O(L) per operation, with no dependence on the number of stored words. That independence is the reason the structure exists.

"How would you delete a word?" Clear the flag, then unlink nodes on the way back up while they have no children and are not word endings.

"How would you return all words with a given prefix?" Walk to the prefix node, then DFS below it.

"What is a compressed trie?" Merge chains of single-child nodes into one edge holding a whole string. Much less memory, and it is what IP routing tables actually use (4.13.4, Chapter 5.3.2).

One thing to volunteer: say that lookup cost depends only on key length, never on the number of keys. That is the property that justifies choosing a trie, and most candidates never mention it.

Recall

  • A trie is a tree where each edge is a character; words sharing a prefix share nodes.
  • Every operation is O(L) in the key length, independent of how many words are stored.
  • The word-end flag is what separates search from startsWith — one line of difference.
  • Map children for sparse or large alphabets, 26-slot array for dense lowercase. Name the trade.
  • A wildcard makes the walk branch, turning it into a DFS that can fail and back out.
  • In Word Search II, store the whole word on the terminal node and null it after reporting, and mark the board itself as the visited set with an undo on the way out.
  • The trie is the pruning: a letter with no matching child kills the branch in one comparison.

Next: 4.15.1 Implement Trie — build the structure, then the other two problems are variations on searching it.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet