Intuition The ONE core ideaA trie is just a tree of letters where walking from the top spells out a prefix, and shared beginnings share the same road. Everything else — the boxes, the arrows, the little flags — exists only to make that walk fast and unambiguous.
Before you can read a single line of trie code, you need a small toolbox of ideas. The parent note quietly assumes all of them. Below we build each one from absolute zero : plain words → the picture → why the trie needs it. Read top to bottom; each idea stands on the one above it.
A character is a single symbol — one letter like c, a, or r. Not a word, not a sentence: one symbol.
Picture a single tile from a Scrabble bag. The word car is three tiles in a row: c, a, r.
Intuition WHY the trie needs thisA trie stores words one letter at a time . Its whole design — one edge per character — only makes sense if we agree that a word is a sequence of individual characters we can step through one by one.
The set of allowed characters is called the alphabet , written with the Greek letter Σ Σ = { a , b , c , … , z } Σ 26 members. When the parent note writes "Σ
Definition String and lengthA string is an ordered list of characters, e.g. "card". Its length , written L how many characters it contains . For "card", L = 4
Look at the figure: the word card is drawn as four tiles left-to-right. The number under the row, L = 4
L one step per character . So the number of steps equals the number of characters, which is exactly L O ( L ) is the length. Meet L O ( L )
Definition Big-O, informallyO ( something ) "as the input grows, how does the work grow?" It ignores constant factors and cares only about the shape of growth.
Imagine timing a task for inputs of size 1, 2, 3, … and plotting the dots.
O ( L ) straight line : double the letters, double the work.O ( log N ) flattens out : doubling N O ( N ) N N
Intuition WHY the topic needs Big-OThe entire selling point of a trie is "O ( L ) independent of N ". You cannot appreciate that sentence without knowing O growth shape and that N
N number of words stored.L length of one word being queried.Σ alphabet size (26 for a–z).
Picture a light switch: up (True) or down (False).
Intuition WHY the trie needs thisEach node carries a flag called ==isEnd==. It is a boolean: True means "a complete word ends right here", False means "this is just a spot along the way". Both search and startsWith ultimately return a boolean answer to a yes/no question. So the whole trie speaks in booleans.
A map stores key → value pairs and lets you look a value up by its key instantly. Ask "what's under key c?" and it hands you the answer without scanning.
Picture a wall of labelled mailboxes: the label is the key , what's inside is the value . You walk straight to the c box; you don't open every box.
Intuition WHY the trie needs thisEvery node holds children: map<char, TrieNode>. The key is a character (c), the value is the child node you reach by following that letter. When code asks if c not in node.children, it is asking the mailbox wall: "is there a box labelled c?" — an instant check. This is what makes each step of the walk fast.
If you already know the Hash Table , a map is exactly that: instant lookup by key. A trie is, in a sense, a hash table chained into a tree .
This is the biggest idea. Build it slowly.
Definition Tree vocabulary
A tree is a branching structure that never loops back on itself.
The root is the single starting point at the top.
A node is one junction/box in the tree.
An edge is a connection between a parent node and one child.
A child is a node hanging directly below another; the one above is its parent .
A leaf is a node with no children (a dead end).
In the figure, follow the colours: the root sits at top. An edge (arrow) carries a single character. Walk root → c → a → r and the path you traced spells the prefix car. Note the node after r has two children (d and e) — one parent, several kids, exactly what a map of children allows.
Intuition WHY the trie IS a treeShared beginnings should share a road. car, card, care all begin c-a-r, so they must walk the same three nodes before splitting. A tree is the only shape that lets many paths merge at the start and fan out later — never looping. That merging-then-branching is the entire reason a trie beats a plain list.
Common mistake "A word ends only at a leaf."WHY it feels right: in many trees the real data sits at the dead-ends. WHY it's wrong here: car is a valid word but is not a leaf — it has child d (for card). So we cannot use "leaf" to mean "word". That is precisely why we need the separate boolean flag isEnd from idea #4.
The empty string "" is a string with zero characters, length L = 0
Picture the row of tiles from figure 1 — now with no tiles at all . That "nothing yet" is where the root lives.
The root represents "" — you haven't spelled anything yet. Every word's walk begins from this "empty" starting point, then adds letters one edge at a time. Without a well-defined "start with nothing" node, the first character would have nowhere to attach.
A prefix is any beginning-chunk of a word. c, ca, car are all prefixes of card. A full word is the whole thing, marked with isEnd = True.
The figure shows the card path. Teal circles mark prefixes (c, ca, car) — real spots on the road but no flag. The orange flag at d marks the full word card.
Intuition WHY this distinction is the heart of the topicsearch("ca") and startsWith("ca") walk the exact same path yet give different answers. ca is a valid prefix (the road exists) but not a word (no flag planted). The single boolean isEnd is what separates "there is a road here" from "a word ends here". Mixing these two up is the #1 trie bug — and now you can see why they differ.
Prefix question (startsWith) ::: "does a road reach here?" → return True if the walk didn't break.
Word question (search) ::: "is a flag planted here?" → return node.isEnd.
Definition Depth-first traversal, informallyTo explore a whole subtree, DFS (depth-first search ) means: go down one branch as far as it goes, then back up and try the next branch, until you've visited every node.
Picture exploring a cave: follow one tunnel to its end, backtrack, take the next tunnel — never skipping any.
Intuition WHY autocomplete needs itAutocomplete walks to the ca node, then must collect every word underneath: car, card, care. Visiting "everything below a node" is exactly what DFS does. You don't need to master DFS yet — just know that "explore the whole subtree" has a standard name and it's coming.
TRIE insert search startsWith
Read top-down: characters make strings, strings have prefixes; booleans make the isEnd flag; maps + trees make the children structure; together they build the trie, whose cost is understood through Big-O, and whose autocomplete leans on DFS.
Related deeper structures you'll meet later (do not worry about them now): the Radix Tree (Compressed Trie) squeezes single-child chains, the Suffix Tree stores endings instead of beginnings, Longest Prefix Match and Edit Distance power routing and spell-check, and a Binary Search Tree is the string structure a trie out-races.
Read each question, answer aloud, then reveal. If any trips you, re-read that numbered section.
A character is one single symbol, e.g. the letter c — not a whole word.
A string of length L an ordered list of L "card" has L = 4
O ( L ) the work grows as a straight line in the number of characters — one step per letter.
N L Σ number of words, length of one word, and alphabet size (26 for a–z).
A boolean is a yes/no switch: only True or False.
A map (children) does what stores key → value and lets you look up a value instantly by its key; here key = character, value = child node.
The root of a trie represents the empty string "" — the "nothing spelled yet" starting point.
A leaf is a node with no children; not the same as "a word ends here".
Why can't "leaf = word" because car is a word yet has child d (for card), so it's internal, not a leaf — we need the isEnd flag.
A prefix vs. a full word a prefix is any beginning-chunk (road exists); a full word additionally has isEnd = True (flag planted).
search vs. startsWith differ bysearch asks "is a flag here?" (isEnd); startsWith asks "does the road reach here?" (True).
DFS means go down one branch fully, backtrack, try the next — visiting every node of a subtree; used for autocomplete.
