The root is the empty prefix; character-labeled edges make each root-to-node path a prefix. Nodes store a children map and terminal marker/payload. Insert creates missing edges, search also checks terminal, and prefix lookup only requires the path.
Recognition signals
Many strings share prefixes and are queried repeatedly.
Full-word membership must be distinguished from prefix existence.
A character DFS should match many dictionary words at once.
Query cost should follow query length rather than dictionary size.
Autocomplete, longest-prefix, or dictionary pruning is required.
False friends
Signal
Why it is different
One fixed pattern
A single-pattern method such as KMP uses less memory.
Exact membership only
A hash set gives expected O(L) with a simpler and often smaller representation; Trie earns its keep through prefixes.
A fixed child array for a huge sparse alphabet
Allocating the full alphabet per node wastes space; use a map or compressed trie.
Core invariant
Every Trie node denotes one unique prefix; its children are exactly the next characters occurring after that prefix in inserted words, and terminal is true only at complete word ends.
State, transition, and processing order
Item
Definition
State
Current Trie node, next character position, and each node's children/terminal/optional payload.
Transition
For character ch, follow children[ch]. Insertion creates a missing edge; lookup fails immediately when the edge is absent.
Frontier / order
A single query follows one prefix path. Combined with grid/backtracking search, a Trie node compresses the remaining candidate words into its subtree.
Python skeleton
class TrieNode:
def __init__(self):
self.children = {}
self.terminal = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.terminal = True
def _walk(self, text):
node = self.root
for ch in text:
if ch not in node.children: return None
node = node.children[ch]
return node
def search(self, word):
node = self._walk(word)
return bool(node and node.terminal)
def starts_with(self, prefix):
return self._walk(prefix) is not None
Correctness sketch
Insertion creates or reuses one edge per character; induction makes the terminal path spell exactly the inserted word.
walk follows only an edge matching the next character; a missing edge proves no inserted word has that prefix.
After a full path, terminal distinguishes a complete inserted word from a path that only prefixes longer words, making both query forms correct.
Complexity
Time
Space
Parameters
Expected O(L) per insert/search/prefix with hash-mapped children
O(T), where T is the number of distinct prefix-character nodes, at most total inserted characters
L is operation string length and T deduplicated prefix nodes.
Edge cases
whether the empty string is a word
case and Unicode normalization
duplicate insertion
deletion with shared prefixes
terminal nodes that also have children
recursive enumeration of autocomplete output
Error patterns
Pattern
Why it fails / fix
Checking only path existence in search
That incorrectly accepts strings that are merely prefixes; full-word search must check terminal.
Requiring terminal for starts_with
A valid prefix need not itself be an inserted word.
Hard-coding 26 children for every alphabet
Large or noncontiguous character domains waste memory or produce invalid indexing.
Restarting at root during every DFS step
Carry the current Trie node so extending a path costs one edge, not a repeated prefix walk.
Selection and exclusion rules
Choose Trie when prefix queries or shared pruning create real value.
Use an array for a small dense alphabet and a map for a sparse one.
Keep terminal and prefix semantics explicit.
When composing with backtracking, carry the node rather than re-searching the whole prefix.
Related templates
Relation
Template
Boundary
Original micro-example
Part
Detail
Result
search('tea') and starts_with('te') are true, while search('te') is false.
Setup
Insert 'tea' and 'team'.
Trace
Both words share t-e-a; the a-node is terminal and still has child m.
Recall prompts
What distinct facts do terminal and children represent?
When is a hash set better than a Trie?
Why should a Trie-guided DFS carry the current node?