What Is a Trie? Structure & Intuition
Visual Representation
Read aloud is unavailable in this browser.
Seeing the Structure
Tries are inherently visual data structures. Unlike hash tables (where the internal organization is essentially random) or balanced trees (where the shape depends on insertion order), a trie's shape directly reflects the data it contains.
When you look at a trie diagram, you're seeing the prefix relationships in your data made visible. Shared prefixes appear as shared paths. Word boundaries appear as marked nodes. The structure tells a story about the strings it holds.
This page develops your ability to visualize tries—to draw them, read them, and think in terms of their visual structure.
By the end of this page, you will be able to draw trie diagrams from a set of words, read trie diagrams to extract stored words, visualize trie operations as they happen, and develop mental models for reasoning about trie behavior without pen and paper.
Standard Trie Diagram Notation
Let's establish consistent notation for trie diagrams. This notation is used throughout the literature and in technical interviews:
Node representation:
- Circles or boxes represent nodes
- The root node is typically drawn at the top (inverted tree style)
- End-of-word nodes are marked with a special indicator: double circle, asterisk (*), or filled circle
Edge representation:
- Lines connecting nodes represent edges
- Each edge is labeled with a single character
- Edges are typically arranged left-to-right in alphabetical order
Path representation:
- A path from root to any node spells a prefix
- A path from root to an end-of-word node spells a complete word
Example: Trie for {the, there, their, them, they}
[root]
|
t
|
h
|
e* ← 'the' ends here
/ |
i m* r
| |
r* e*
(their) (there)
↓
[they: continue from 'the' with y*]
Actually, let me draw this more accurately:
[root]
|
t
|
h
|
e* ←────── 'the'
/ | \\
i m* r y*
| | ↑
r* e* 'they'
↑ ↑
'their' 'there'
↑
'them'
To extract all words from a trie diagram:
- Start at the root
- Follow each path, collecting edge labels
- When you reach an end-of-word node (*), the collected labels form a stored word
- Continue to explore all branches before backtracking
This is essentially a DFS traversal of the trie.
Building a Mental Picture: The Tree of Prefixes
The most powerful way to visualize a trie is as a hierarchy of prefixes. Each level of the tree adds one character to the prefixes above it.
Level-by-level thinking:
Level 0 (root): "" ← empty prefix, all strings start here
│
└── Level 1: "c", "d" ← first characters of stored strings
│
└── Level 2: "ca", "do" ← two-character prefixes
│
└── Level 3: "car", "cat", "dog" ← three-character prefixes
Each node answers the question: "How many and which words share this prefix?"
- The root: all words share the empty prefix (= all words in trie)
- The 'c' node: all words starting with 'c'
- The 'ca' node: all words starting with 'ca'
- The 'car' node: all words starting with 'car'
Subtrie visualization:
Every node is the root of a subtrie containing all words with a specific prefix:
Full Trie Subtrie at 'car'
───────── ────────────────
[root] [car-node]
/ \\ /
c d d* e*
| | |
a o* f
/ \\ | |
r* t* g* u
/ \\ |
d* e* l*
|
f Words in subtrie: {card, care, careful}
| These are EXACTLY the words with prefix 'car'
u
|
l*
Full trie has: {car, card, care, careful, cat, do, dog}
When answering 'find all words starting with X', visualize zooming into the subtrie rooted at the X-node. That subtrie contains exactly what you need—nothing more, nothing less. This mental zoom is the intuitive basis for efficient prefix queries.
Visualizing Insertion: Growing the Tree
When you insert a word, you're growing the tree. The visual process:
- Navigate existing paths: Follow edges that already exist (no changes to structure)
- Create new branches: When no edge exists for the next character, add a new node and edge
- Mark terminus: Set end-of-word on the final node
Let's visualize inserting "care" and then "careful" into a trie that already has "car":
Starting state - trie contains only "car":
[root]
|
c
|
a
|
r* ← end-of-word (car)
Nodes: 4 (root + c + a + r) End-of-word nodes: 1 (r-node)
Insertion always follows the same visual pattern: trace down as far as existing edges allow, then grow a straight chain of new nodes for remaining characters. The trie never restructures existing paths—new words only add new branches.
Visualizing Search: Traversing the Tree
Search is a read-only traversal. You're asking: "Does this path exist, and is the endpoint marked?"
Visual model: Imagine highlighting nodes as you traverse, like a cursor moving through the tree.
Searching for "careful" in trie {car, care, careful, cat}:
Step 1: At root, looking for 'c' Step 2: At c-node, looking for 'a'
[ROOT] ← cursor [root]
/ \\ |
c ... [C] ← cursor
| |
a a
... ...
Step 5: At e-node, looking for 'f' Step 8: At l-node, string exhausted
[root] [root]
| |
c c
| |
a a
/ \\ |
r* t* r*
| |
[E]* ← cursor e*
| |
f f
| |
u u
| |
l* [L]* ← cursor, IS end-of-word!
Result: FOUND! 'careful' exists.
Searching for "car" in the same trie:
[root]
|
c
|
a
/
r* t*
↑
cursor stops here
String exhausted: 'c-a-r'
Is this node end-of-word? YES (*)
Result: FOUND!
Searching for "ca" (not in trie):
[root]
|
c
|
a ← cursor stops here
/
r* t*
String exhausted: 'c-a'
Is this node end-of-word? NO (no *)
Result: NOT FOUND (prefix exists, but not a stored word)
Visualizing Prefix Queries: The Subtrie Harvest
Prefix queries (autocomplete, startsWith) are visually elegant: navigate to the prefix node, then harvest the entire subtrie.
Finding all words starting with "ca":
Step 1: Navigate to 'ca' Step 2: Harvest subtrie
[root] [root]
| |
c c
| |
[a] ← reached prefix node [a] ← subtrie root
/ \\ ╔═══════╗
r* t* ║ / \\ ║
/ \\ ║r* t*║ ← this entire box
d* e* ║/ \\ ║ is the 'ca' subtrie
| ║d* e* ║
f ║ | ║
| ║ f ║
u ║ | ║
| ║ u ║
l* ║ | ║
║ l* ║
╚═══════╝
Words in subtrie:
• r* → 'car'
• r → d* → 'card'
• r → e* → 'care'
• r → e → f → u → l* → 'careful'
• t* → 'cat'
Result: {car, card, care, careful, cat}
Notice the visual boundary around the subtrie. Every word inside that boundary starts with 'ca'. Every word outside doesn't. The trie's structure physically separates matching words from non-matching ones. This is why prefix queries are efficient—you don't examine non-matching words at all.
Comparing Trie Shapes: How Data Affects Structure
The shape of a trie directly reflects the prefix patterns in your data. Let's compare different types of data:
Words: {pre, predict, prediction, predictive, predictable}
[root]
|
p
|
r
|
e* ────────────── 'pre'
|
d
|
i
|
c
|
t* ───────────── 'predict'
/ |
i a i
| | |
o b v
| | |
n* l e*
|
e*
Characteristics:
- Very deep, narrow structure
- Long shared stem (p-r-e-d-i-c-t)
- Branching only at the end
- High compression ratio
- 5 words, only 18 nodes
By looking at a trie's shape, you can estimate its efficiency: • Tall and narrow → high compression, shared prefixes • Short and wide → low compression, distinct prefixes • Balanced mix → typical dictionary data
If your data produces a 'short and wide' trie, consider whether a hash table might be more appropriate.
ASCII Art Conventions for Technical Communication
In technical interviews, documentation, and code comments, you'll often need to draw tries using ASCII characters. Here are standard conventions:
Basic ASCII trie symbols:
[root] or (root) or just * ← root node
| ← single vertical edge
a ← edge label (character)
|
b* ← end-of-word node (asterisk suffix)
/ \\ ← branching to multiple children
c d ← sibling edges
│ ← alternative: Unicode box drawing
├── ← branch with continuation
└── ← final branch
Compact horizontal format:
root ─c─ a ─┬─ r* ─┬─ d*
│ └─ e* ─ f ─ u ─ l*
└─ t*
Indented format (good for code comments):
// Trie contents: {car, card, care, careful, cat}
// (root)
// └─ c
// └─ a
// ├─ r* (car)
// │ ├─ d* (card)
// │ └─ e* (care)
// │ └─ f
// │ └─ u
// │ └─ l* (careful)
// └─ t* (cat)
On a whiteboard: • Draw root at the top • Use simple circles for nodes • Double-circle or fill for end-of-word nodes • Write edge labels on the lines • Arrange children left-to-right alphabetically • Don't cram—spread out for clarity
Practice drawing tries quickly and neatly—it's a valuable skill.
KEEP LEARNING
There’s more to understand.
You’re reading the introduction. Create a free account to read the complete lesson, save notes and keep track of your progress.