In a trie, what bug appears if nodes carry no end-of-word marker?

juniormust knowfreq 60%

answer

a walk that never falls off
the search says yes too often
prefix question versus word question
what separates 'car' from 'carpe'
one terminal fact stored per node

basics

~20 s

Without an end-of-word marker a trie reports that a path of symbols exists, not that a key ended there. Insert 'carpet' and a search for 'car' walks a valid path and wrongly reports a match — as does every proper prefix.

solid answer

~50 s

A trie node stores no string of its own — the path from the root to the node spells the prefix. So walking a query symbol by symbol without falling off proves only that some stored key continues through that path, which answers the prefix question, not the membership question. If search returns true at the end of a successful walk, then after inserting carpet the keys c, ca, car, carp and carpe all report present. The fix is one extra fact per node: a terminal flag (or a value slot) set by insert on the final node. Membership walks and then checks the flag; a prefix query walks and ignores it. Note that "a key ends at a leaf" is not a valid substitute — with car and carpet both stored, car ends at an internal node.

A trie node stores no string of its own — the path from the root to the node spells the prefix. So walking a query symbol by symbol without falling off proves only that *some* stored key continues through that path, which answers the prefix question, not the membership question. If search returns true at the end of a successful walk, then after inserting `carpet` the keys `c`, `ca`, `car`, `carp` and `carpe` all report present. The fix is one extra fact per node: a terminal flag (or a value slot) set by insert on the final node. Membership walks and then checks the flag; a prefix query walks and ignores it. Note that "a key ends at a leaf" is not a valid substitute — with `car` and `carpet` both stored, `car` ends at an internal node.

code

pseudocode · 8 lines

pseudocode

// membership check over a trie -- contains the bug
node = root
for i in 0..length(word)-1
    c = word[i]
    if node.children[c] == null
        return false
    node = node.children[c]
return true          // the walk survived -- but did a key END here?

go deeper

for a junior

Be ready to state that a node must mark whether a key ends there, and to give the concrete failure out loud: insert one longer key and every one of its prefixes starts answering yes.

for a middle

Explain that path existence and key membership are two distinct queries over the same structure, and that the terminal flag is the only thing separating them. Show how insert, search and prefix search each use or ignore it.

for a senior

Show the operational consequence: deletion, duplicate counting and prefix counts all hang off the same marker, and a missing one yields silent false positives that get reported as data corruption rather than as a lookup bug.

for a principal

Own the interface decision: whether the structure exposes membership and prefix search as two clearly named operations or one ambiguous lookup, because an overloaded lookup is how this bug spreads across teams that never read the implementation.

What a trie node represents

A trie stores a set of strings by their symbols rather than by a hash of the whole string. Each edge carries one symbol; the path from the root to a node spells a prefix, and that prefix is the node's identity. The root spells the empty string. A node stores no string of its own, so the total number of nodes equals the number of distinct prefixes across the key set — not the number of keys.

Two questions, one structure

A trie can be asked two different things about a query string s:

Is s a stored key? — membership.
Is s a prefix of at least one stored key? — prefix query.

Walking s one symbol at a time from the root and never falling off a missing edge answers question 2 only. A successful walk proves a path exists, which proves some stored key continues through that path. It says nothing about whether anything stopped there.

The bug

Insert carpet into an empty trie: six nodes appear, spelling c, ca, car, carp, carpe, carpet. Now search for car. Every step of the walk exists, so a search that returns true at the end of a successful walk reports car as stored — although it was never inserted. This is not a one-off. Every proper prefix of every stored key becomes a false positive, so a set of fifty thousand keys silently gains hundreds of thousands of phantom members. Spell-checkers accept non-words, membership filters admit unregistered keys, de-duplication drops entries it should have kept — with no error, no crash, and a structure that looks fine in a debugger.

The fix, and why it lives on the node

Give each node one extra fact: a terminal flag meaning "a stored key ends here". Insert sets it on the last node of the walk. Membership walks and then checks the flag. The prefix query walks and ignores it. When the trie is a map rather than a set, a value slot plays the same role — a filled slot is the marker.

Why "keys end at leaves" is not a fix

The common wrong repair is to say a key ends wherever the path ends, that is, at a leaf. That breaks exactly when one key is a prefix of another: with car and carpet both stored, car ends at an internal node that still has a child. Only prefix-free key sets put every key at a leaf, and prefix-freeness is normally manufactured by appending a sentinel symbol that never occurs in real keys — which is an end-of-word marker wearing a different hat.

Deletion depends on the marker too

Removing a key is: walk to its final node, clear the marker, then prune upward while the current node has no children and is not itself marked, stopping at the first node that branches or terminates another key. Without a marker there is no way to distinguish an internal node that is also a key from a pure branch point, so deletion either destroys longer keys or leaves paths that keep answering true.

Useful variants of the marker

A count instead of a boolean makes the trie a multiset: repeated inserts increment, deletes decrement, and the key is present while the count is positive.
A subtree key count, maintained on insert and delete, answers "how many stored keys start with this prefix" in O(L) without enumerating them — the basis of prefix ranking.
A payload slot turns the set into a map from key to value, and doubles as the marker.

What it costs

Membership is O(L) symbol steps for a query of length L, independent of how many keys the trie holds; the marker check is a single O(1) test at the end and changes nothing asymptotically. The prefix query is the same walk without that test. Worth noting for the comparison people reach for: a hash set is also O(L) for membership in honest accounting, because it must read all L symbols to hash them and compare the full key on a hit. The marker is therefore not a price the trie pays for speed — it is the minimum bookkeeping that makes membership correct in a structure whose nodes are prefixes rather than keys.

The one-line takeaway

In a trie, a successful path is evidence about prefixes; only a marker is evidence about keys.

**What a trie node represents** A trie stores a set of strings by their symbols rather than by a hash of the whole string. Each edge carries one symbol; the path from the root to a node spells a prefix, and that prefix *is* the node's identity. The root spells the empty string. A node stores no string of its own, so the total number of nodes equals the number of **distinct prefixes** across the key set — not the number of keys. **Two questions, one structure** A trie can be asked two different things about a query string `s`: 1. *Is `s` a stored key?* — membership. 2. *Is `s` a prefix of at least one stored key?* — prefix query. Walking `s` one symbol at a time from the root and never falling off a missing edge answers **question 2 only**. A successful walk proves a path exists, which proves some stored key continues through that path. It says nothing about whether anything stopped there. **The bug** Insert `carpet` into an empty trie: six nodes appear, spelling c, ca, car, carp, carpe, carpet. Now search for `car`. Every step of the walk exists, so a search that returns true at the end of a successful walk reports `car` as stored — although it was never inserted. This is not a one-off. *Every proper prefix of every stored key becomes a false positive*, so a set of fifty thousand keys silently gains hundreds of thousands of phantom members. Spell-checkers accept non-words, membership filters admit unregistered keys, de-duplication drops entries it should have kept — with no error, no crash, and a structure that looks fine in a debugger. **The fix, and why it lives on the node** Give each node one extra fact: a terminal flag meaning "a stored key ends here". Insert sets it on the last node of the walk. Membership walks and then checks the flag. The prefix query walks and ignores it. When the trie is a map rather than a set, a value slot plays the same role — a filled slot *is* the marker. **Why "keys end at leaves" is not a fix** The common wrong repair is to say a key ends wherever the path ends, that is, at a leaf. That breaks exactly when one key is a prefix of another: with `car` and `carpet` both stored, `car` ends at an internal node that still has a child. Only **prefix-free** key sets put every key at a leaf, and prefix-freeness is normally manufactured by appending a sentinel symbol that never occurs in real keys — which is an end-of-word marker wearing a different hat. **Deletion depends on the marker too** Removing a key is: walk to its final node, clear the marker, then prune upward while the current node has no children *and* is not itself marked, stopping at the first node that branches or terminates another key. Without a marker there is no way to distinguish an internal node that is also a key from a pure branch point, so deletion either destroys longer keys or leaves paths that keep answering true. **Useful variants of the marker** - A **count** instead of a boolean makes the trie a multiset: repeated inserts increment, deletes decrement, and the key is present while the count is positive. - A **subtree key count**, maintained on insert and delete, answers "how many stored keys start with this prefix" in O(L) without enumerating them — the basis of prefix ranking. - A **payload slot** turns the set into a map from key to value, and doubles as the marker. **What it costs** Membership is O(L) symbol steps for a query of length L, independent of how many keys the trie holds; the marker check is a single O(1) test at the end and changes nothing asymptotically. The prefix query is the same walk without that test. Worth noting for the comparison people reach for: a hash set is *also* O(L) for membership in honest accounting, because it must read all L symbols to hash them and compare the full key on a hit. The marker is therefore not a price the trie pays for speed — it is the minimum bookkeeping that makes membership *correct* in a structure whose nodes are prefixes rather than keys. **The one-line takeaway** In a trie, a successful path is evidence about prefixes; only a marker is evidence about keys.

How does a prefix query differ from a membership query in the same trie?
A prefix query needs only the walk to succeed: if you can spell the string edge by edge, at least one stored key starts with it. Membership needs that same walk plus a terminal marker on the final node. One structure answers both, and conflating them is precisely what produces a false positive on every proper prefix of every stored key.
How would you delete a key from a trie without breaking the keys around it?
Walk to the final node and clear its terminal marker first — that alone makes the key absent. Then prune upward, removing a node only while it has no children and is not itself marked, and stop at the first node that branches or terminates another key. Removing the whole path instead would delete every key that shares that prefix.
What do you gain by storing a count rather than a boolean at each node?
A count turns the set into a multiset: inserting the same key twice increments it, deleting decrements, and the key is present while the count stays positive. A separate subtree-count field, updated on insert and delete, additionally answers "how many stored keys start with this prefix" in O(L) without walking the subtree.

Walking a corridor and finding every door unlocked tells you someone can get further down the hall. It does not tell you that any room you passed is one you actually rented; the marker is the nameplate.

saying these in an interview costs you the question

Says reaching the last symbol proves the key is stored
Treats prefix search and exact search as one query
Claims complete keys only ever end at leaf nodes
Deletes a key by removing every node on its path
Thinks each node stores the whole string it represents

In a trie, what bug appears if nodes carry no end-of-word marker?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

§ context

▾related questions3 questions

▾related topics3 topics

answer

go deeper

context