Visual walkthrough — Trie (prefix tree) — insert, search, startsWith, applications (autocomplete, spell check)

We will grow a trie for the tiny dictionary $\{\text{car},\text{card},\text{care},\text{dog}\}$ and then run every kind of query against it, including the tricky ones that fail.

---

Step 0 — What is a "node" and what is an "edge"? (zero assumed)

Before drawing anything, we must agree on the two shapes we will draw.

• A node is a circle. It stands for one prefix — a string of letters you have spelled so far by walking down from the top.
• An edge is a line joining a parent circle to a child circle, and it is labeled with exactly one letter. Walking down an edge means "append this letter to the prefix."

Inside every node we also keep one true/false switch:

Read the figure: the gray circle at top is the root (""), the line below it is an edge, and its label is the single letter it carries. Nothing is green yet because no word has been planted.

---

Step 1 — Insert car: carve a brand-new road

WHAT. We add our first word, car, into the empty trie.

WHY. Nothing exists yet, so every letter must create a new node. This is the "no shared prefix" case — the simplest one, and the base we build everything on.

HOW, letter by letter. Start the finger at the root. For each letter we ask "does a child edge with this letter already exist?" — here the answer is always no, so we create it and step down:

$$\underset{\text{root}}{\underbrace{\text{""}}}\stackrel{\text{c}}{\to }\underset{\text{new node}}{\underbrace{\text{"c"}}}\stackrel{\text{a}}{\to }\underset{\text{new node}}{\underbrace{\text{"ca"}}}\stackrel{\text{r}}{\to }\underset{\text{new node}}{\underbrace{\text{"car"}}}$$

Each arrow is one edge we just created; the label over the arrow is that edge's letter; the string under each node is the prefix that node now represents. After the last letter is consumed we flip the switch on the final node:

$\text{node}.\text{isEnd}\leftarrow \text{true}$

The $\leftarrow$ means "store true into this field." Only the "car" node turns green.

PICTURE. A single straight chain ""→c→a→r. The last circle is filled green (a word ends there); the middle two are hollow gray (they are only prefixes, not words).

---

Step 2 — Insert card: reuse the road, don't rebuild it

WHAT. Add card.

WHY. card starts with car, which already exists. This is the whole reason tries are fast — shared prefixes are walked, never duplicated.

HOW. Finger at root. Now the "does this child exist?" question flips to yes three times in a row, so we reuse — we just step down existing edges:

$$\text{""}\underset{\text{these 3 edges already exist}\Rightarrow \text{reuse}}{\underbrace{\stackrel{\text{c}}{\to }\text{"c"}\stackrel{\text{a}}{\to }\text{"ca"}\stackrel{\text{r}}{\to }\text{"car"}}}\underset{\text{new: only this edge is created}}{\underbrace{\stackrel{\text{d}}{\to }\text{"card"}}}$$

Only the final d edge and its "card" node are new. Then "card".isEnd ← true.

Notice what just happened to the "car" node: it now has a child (d), yet it is still green. A green node with children is completely normal.

PICTURE. The chain from Step 1 is untouched (drawn in the same blue); a single orange edge d sprouts below "car" to a new green "card". Two green nodes now sit on one path — car (internal) and card (leaf).

---

Step 3 — Insert care: a node can branch into many children

WHAT. Add care.

WHY. To show a node holding more than one child. The "car" node already has child d; now it also needs child e.

HOW. Reuse c→a→r again. At "car" we ask "is there an e child?" — no (there is only d). So create e:

$$\text{"car"}\stackrel{\text{e}}{\to }\text{"care"},\text{"car".children}=\{\underset{\to \text{card}}{\underbrace{\text{d}}},\underset{\to \text{care}}{\underbrace{\text{e}}}\}$$

The set notation on the right lists the two child-letters "car" now owns. A node's children is a map, so it can fan out to as many letters as needed. Then "care".isEnd ← true.

PICTURE. Below "car" the tree forks: one orange edge d to green "card", one orange edge e to green "care". This is the first branch — the shared road c-a-r splits into two endings.

---

Step 4 — Insert dog: a totally separate road from the root

WHAT. Add dog.

WHY. To cover the case of no shared prefix at all — the word disagrees with everything from letter one.

HOW. Finger at root. Ask "does root have a d child?" — no (root only has c). So a brand-new branch grows straight off the root:

$$\text{""}\stackrel{\text{d}}{\to }\text{"d"}\stackrel{\text{o}}{\to }\text{"do"}\stackrel{\text{g}}{\to }\text{"dog"}$$

Three new nodes, and "dog".isEnd ← true.

PICTURE. The root now has two children: c (the whole car-family on the left) and d (the dog chain on the right). Different first letters ⇒ subtrees that never touch. The full dictionary trie is now complete.

---

Step 5 — search: walk, then ask "is a word here?"

WHAT. Run search("car") and search("ca") on the finished trie.

WHY. To expose the single most important subtlety: reaching the end of a path is not the same as finding a word. The final isEnd check decides it.

HOW. search walks the letters. If a letter's child is missing, return false (road broke). If we survive to the end, we return the switch at the node we landed on:

$$\text{search}(w)=\{\begin{array}{ll}\text{false}& \text{if any edge on the way is missing (road broke)}\\ \text{node}.\text{isEnd}& \text{if we reached the end node}\end{array}$$

• search("car"): walk c→a→r, all edges exist, land on the green node ⇒ return isEnd = true. ✅
• search("ca"): walk c→a, both edges exist, land on "ca" — but that circle is gray ⇒ return isEnd = false. We never planted a word ca. ❌

PICTURE. Two finger-walks drawn as arrows: the green arrow stops on a green node (car → true); the red arrow stops on a gray node (ca → false), with a big ✗ showing "path exists but no flag."

---

Step 6 — startsWith vs the broken-road case

WHAT. Run startsWith("ca") (succeeds) and search("ban") (fails at letter 0).

WHY. startsWith is the same walk as search but asks a different final question — it does not read isEnd. And we must see what happens when the road breaks immediately.

HOW.

$$\text{startsWith}(p)=\{\begin{array}{ll}\text{false}& \text{if any edge is missing}\\ \text{true}& \text{if the whole path }p\text{ exists (ignore isEnd)}\end{array}$$

• startsWith("ca"): walk c→a, both edges exist ⇒ return true. It does not matter that "ca" is gray — some word (car, card, care) continues through it. ✅
• search("ban"): at the root, ask for a b child ⇒ missing ⇒ return false at letter 0, before walking any further. ❌

The one-line contrast, side by side:

$$\underset{\text{"is this a WORD?"}}{\underbrace{\text{search}\Rightarrow \text{return node.isEnd}}}\text{vs}\underset{\text{"is this a ROAD?"}}{\underbrace{\text{startsWith}\Rightarrow \text{return true}}}$$

PICTURE. Left: a green arrow walks c→a and simply stops with a ✓ (road exists — startsWith happy on a gray node). Right: a red arrow tries b at the root, hits a wall (no b edge) and returns false immediately.

---

The one-picture summary

Everything above — the four inserts, the reuse of shared prefixes, and the three query behaviors — compressed into a single labeled diagram.

Green nodes are where words end (car, card, care, dog); gray nodes are prefixes-only. The blue path is the shared c-a-r road; orange edges are where words diverge. Overlaid arrows recall the three questions: plant (insert), flag here? (search reads the green switch), road here? (startsWith ignores color).

Recall Feynman: tell the whole walkthrough to a friend

We started with one empty circle — the trunk of a tree that has spelled nothing. To add car, no branches existed, so we carved c, then a, then r, and stuck a little green flag on the r circle meaning "a real word ends here." To add card, the c-a-r road already existed, so we just walked it and grew one new d twig with its own flag — reusing the road is the whole trick. care grew a second twig e off the same r, so one circle can split many ways. dog disagreed from the very first letter, so it became a separate branch straight off the trunk. Then querying is just walking the letters like following a map: to check if a word exists you walk there and check for a green flag — car has one (yes!), ca reaches a real circle but it's gray (no word, just a prefix). To check if a prefix exists you walk there and don't care about the flag at all — ca is a real road so "yes," while ban dies instantly because the trunk has no b branch. Same walk every time; only the final question changes.

---

Active Recall

---

See also: Radix Tree (Compressed Trie) (collapses these single-child chains), Suffix Tree, DFS (used by autocomplete over a subtree), Longest Prefix Match, Hash Table and Binary Search Tree (the rivals with no prefix structure), and Edit Distance for spell-check suggestions.