Intuition What this page is forThe parent note taught you the three operations. But a topic is only understood when you have met every kind of input it can throw at you. This page builds a scenario matrix — a checklist of every situation class — then works one example per cell so you never meet a case you have not seen.
Before we start, a word we will use constantly. A node is one spot on the tree (a place you can stand). An edge is a labelled arrow between two nodes, carrying one character. The root is the top node, standing for the empty string "". The flag ==isEnd== is a little ✅ on a node meaning "a complete word finishes exactly here". Keep these four words in your head; every example below only ever walks edges , stands on nodes , and checks flags .
Every problem a trie can throw at you falls into one of these cells . The matrix is our map — each worked example below is tagged with the cell it fills.
Cell
Class of scenario
What makes it tricky
Filled by
A Insert into empty trie
no shared road yet — every char is new
Ex 1
B Insert sharing a prefix
reuse existing road, branch late
Ex 2
C search a word that IS presentmust end on isEnd = True
Ex 3
D search a proper prefix (present as road, NOT as word)path exists but isEnd = False
Ex 4
E search a word whose path breaks earlymissing child → fail at char k
Ex 5
F startsWith vs search on same stringsame walk, different final question
Ex 6
G Degenerate input: empty string ""zero characters — the loop never runs
Ex 7
H One word is a strict prefix of another (car ⊂ card)
isEnd on an internal nodeEx 8
I Delete without breaking a longer wordunset flag, prune carefully
Ex 9
J Real-world / exam twist : autocomplete ranking + limiting case (no completions)DFS a subtree, handle the empty result
Ex 10
The running dictionary for most examples is D = { car , card , care , dog }
Ex 1 — Cell A: insert into an empty trie · insert("car")
Forecast: guess before reading — how many new nodes get created, and where does the ✅ land?
Stand on the root. Why this step? Every operation begins at the root because the root is the empty string, and any word is built by adding characters onto the empty string.Char c: root has no child labelled c. Create a node, put an edge c to it, step in. Why? No road exists, so we must lay it — this is the "extend the road" rule.Char a: the c-node has no a-child. Create it, step in. Why? Same rule — still virgin territory.Char r: create the r-node, step in. Why? Last character, still new.Set node.isEnd = True on the r-node. Why? We consumed all of "car"; the word finishes here , so we plant the ✅ flag. Without it, a later search("car") would say False.
Verify: we created exactly L = 3 one flag was set. Time O ( L ) = O ( 3 ) c→a→r chain in magenta with a ✅ on r. ✔
Ex 2 — Cell B + Cell H: insert sharing a prefix · insert("card"), insert("care")
Forecast: when we add card, how many of its 4 characters create new nodes?
Insert card. Walk c→a→r: all three children already exist (from Ex 1), so we reuse them — create nothing, just step in three times. Why? This reuse of a shared prefix is the entire reason tries exist; we never store c-a-r twice.Char d: the r-node has no d-child. Create it, step in, set isEnd = True. Why? Only the new tail d needs a node; card finishes there.Notice car's node still has its ✅. Why does this matter? The r-node is now internal (it has child d) yet is still a word . This is Cell H live in front of you: an internal node carrying isEnd. It proves why "leaf = word" is a bug.Insert care. Walk c→a→r (reuse). The r-node has child d but no e. Create e, step in, set isEnd. Why? A node's children is a map , so r can hold several kids (d and e) — they branch here.
Verify: card added exactly 1 new node (d); care added exactly 1 new node (e). Three words now share the single c→a→r road. Total nodes for { c a r , c a r d , c a r e } c,a,r,d,e) instead of 3 + 4 + 4 = 11 r in the figure.)
Ex 3 — Cell C: search a present word · search("care")
Forecast: does the walk succeed, and what is the final check that returns the answer?
Walk c→a→r. Each child exists → step in. Why? Search is the same traversal as insert, minus the "create" step. We only read the road.Char e: the r-node has an e-child (built in Ex 2) → step in. Why? Path still intact.Return node.isEnd on the e-node. It is True. Why not just return True because the walk finished? Because a finished walk only proves the path exists; we must confirm a word ends here . Here it does.
Verify: search("care") = True. We visited L = 4 O ( L ) care was inserted, so it must be findable. ✔
Ex 4 — Cell D: search a proper prefix that is NOT a word · search("ca")
Forecast: the letters c and a are clearly "in" the trie. So is the answer True? Guess.
Walk c→a. Both children exist → step in. Why? ca is the road walked by car/card/care, so of course the path is present.Return node.isEnd on the a-node. It is FalseWhy? We never called insert("ca"), so no ✅ was ever planted on the a-node.
Verify: search("ca") = False. This is the classic trap: the path exists but no word ends there. Contrast this directly with Ex 6. ✔
Ex 5 — Cell E: search whose path breaks early · search("cat")
Forecast: at which character index does this fail — 0, 1, or 2?
Char c (index 0): exists → step into c-node. Why? Road present so far.Char a (index 1): the c-node has an a-child → step in. Why? Still present (car/card/care use it).Char t (index 2): the a-node's only child is r — no t-child . Return False immediately. Why stop here? The road is broken; there is no possible way any word cat… exists, so we abandon at once — this early exit is why tries prune so hard.
Verify: search("cat") = False, failing at index 2 after visiting 2 nodes (not all 3 chars). ✔ Note we never even looked for a flag — the walk died first.
Ex 6 — Cell F: startsWith vs search on the SAME string · both on "ca"
Forecast: we already know search("ca") = False (Ex 4). What will startsWith("ca") give, and why the difference from identical code ?
startsWith("ca"): walk c→a.Why? Identical traversal to search.Return True — not node.isEnd. Why? startsWith asks a different final question : "does this road exist?" not "does a word end here?". The path survived, so some word (car/card/care) continues through ca. Answer True.
Verify: search("ca") = False but startsWith("ca") = True. Same walk, one line different at the end (return node.isEnd vs return True). This is the whole distinction, isolated. ✔
Ex 7 — Cell G: the degenerate empty string · insert(""), then search("") and startsWith("")
Forecast: the loop for c in word runs zero times when word = "". So where does the code end up standing, and what happens?
insert(""):node.isEnd = True — but node is still the root . So the root's flag gets set. Why? The empty string is a legitimate word finishing at the empty-string node, which is the root itself.search(""):node stays the root, we return root.isEnd. After step 1 that is True. Why? We planted a ✅ on the root, so "" is now a stored word.startsWith("")any non-empty trie: loop runs zero times, node stays root, return True. Why? The empty prefix is a prefix of everything — the root road trivially exists.
Verify: before insert(""), search("") = False (root's flag defaults to False); after, search("") = True. And startsWith("") = True always (even on an empty trie, since the root always exists). The zero-iteration loop is the key mechanism. ✔
Ex 8 — Cell H isolated: does search("card") stay valid after car exists?
Forecast: car sits on an internal node with a ✅. Does that flag accidentally make the walk to card stop short? Guess.
Walk c→a→r. The r-node has isEnd = True (it is the word car). We ignore that flag mid-walk and keep going. Why? isEnd is only consulted at the final node of the query, never mid-traversal. Passing through a word-ending node does not stop us.Char d: r-node has a d-child → step in. Why? The branch we built in Ex 2 is intact.Return d-node's isEnd = True. Why? card was inserted; its own flag lives on the d-node, independent of car's flag.
Verify: both coexist: search("car") = True and search("card") = True, on the same path. Two flags, two words, one shared road. ✔
Ex 9 — Cell I: delete car without destroying card
Forecast: if we "removed car's node and its subtree", what would break? Predict which words survive.
Walk to car's node (r) and set isEnd = False. Why not delete the node? Because the r-node still has children (d for card, e for care). Deleting it would orphan two other words.Ask: can we prune the r-node? Rule: prune a node only if it has no children and its own isEnd is False. Here r still has children d and e → keep it . Why? Pruning a node that others need would corrupt the trie.Walk back up (a, c) checking the same rule. Each still has descendants → keep all. Why? The road is still shared by card and care.
Verify after delete: search("car") = False (flag cleared), yet search("card") = True and search("care") = True (paths untouched). Correct deletion = unset flag + prune only childless, non-word nodes. ✔
Ex 10 — Cell J: autocomplete + the limiting empty case
Statement: on D = { c a r , c a r d , c a r e , d o g } autocomplete("ca"), then the limiting query autocomplete("z").
Forecast: how many completions does "ca" yield, and what should "z" return — an error, or something graceful?
Walk to the a-node (the end of prefix ca). Why? Autocomplete first finds the prefix node , then explores above it. Path c→a exists (Ex 4), so we land on the a-node.DFS the subtree rooted at a (this is depth-first search — go as deep as possible down one branch, then backtrack). At each node with isEnd = True, record prefix + pathSoFar. Why DFS? It visits exactly the relevant subtree and nothing else — we never scan the dictionary.
Down r: r.isEnd = True → record "car".
Continue: r→d, d.isEnd = True → record "card".
Back up, r→e, e.isEnd = True → record "care".
Return ["car", "card", "care"] (3 completions; dog is in a different subtree, never visited). Why is dog skipped? It hangs off a separate d-branch of the root , outside the ca subtree — the prefix walk never reaches it.Limiting case autocomplete("z"): root has no z-child → the prefix walk breaks at char 0 → return [] (empty list), not an error. Why gracefully empty? No path means no word has this prefix; the honest answer is "zero completions".
Verify: len(autocomplete("ca")) = 3 with set {car, card, care}; autocomplete("z") = [] (length 0). Every completion shares the ca road, and the missing-prefix case degrades to an empty list. ✔
Recall Quick self-test across the matrixOn D = { c a r , c a r d , c a r e , d o g } search("ca") ::: False (path exists, no word ends — Cell D)
startsWith("ca") ::: True (road exists — Cell F)
search("cat") ::: False, breaks at index 2 (Cell E)
search("card") after inserting car ::: True — both flags coexist (Cell H)
search("") before any insert("") ::: False (root flag defaults false — Cell G)
autocomplete("z") ::: [] empty list, graceful (Cell J limit)
"Walk the road, check the flag, never invent one you didn't plant." Every cell above is just: does the road exist, and is there a flag where you finally stand?
In search, why do we return node.isEnd instead of True after the walk succeeds? A successful walk only proves the path/prefix exists; a word must end there, which only isEnd confirms.
When deleting a word, when may we prune a node? Only if it has no children AND its own isEnd is False; otherwise other words still need it.
What does insert("") do? The character loop runs zero times, so it sets isEnd = True on the root (the empty-string node).
Why does autocomplete("z") return [] and not crash? The prefix walk finds no z-child, breaks immediately, and returns an empty list — no word has that prefix.
