A Trie Without an End-of-Word Mark

Without the mark, every prefix of a stored word looks like a stored word.

A trie built without an end-of-word mark answers yes when asked for any beginning of a stored word, because a search that only checks whether a path exists cannot tell a word from a prefix of one. This card covers how that mistake arises, what it returns, and the one field and one check that fix it.

A trie is a tree whose root holds no letter and whose every other node stands for one letter, so a stored word is a path from the root. The mistake is natural because the path looks like all the information there is: inserting a word creates its path, so finding the path feels like finding the word. That is the rule for checking a prefix, and code that starts from a prefix check and adds a search often keeps it.

The tree below is the trie after inserting only sung. Every node on the path was created by that one word, and nothing in the tree says where the word ends.

The trie after inserting only sung, with no end-of-word mark

root
- s
  - u
    - n
      - g, the word ends here, but nothing records it

The listing builds that trie twice, once without the mark and once with it, and searches both for the same four strings. Without the mark, the search returns true when the path exists, so sun and s come back as stored words. With the mark, the search also requires the last node to be marked, and only sung passes.

missing_mark.pypy

class UnmarkedNode:
    def __init__(self):
        self.children = {}


class MarkedNode:
    def __init__(self):
        self.children = {}
        self.is_word = False


def insert_unmarked(root, word):
    node = root
    for letter in word:
        node = node.children.setdefault(letter, UnmarkedNode())


def search_unmarked(root, word):
    node = root
    for letter in word:
        if letter not in node.children:
            return False
        node = node.children[letter]
    return True


def insert_marked(root, word):
    node = root
    for letter in word:
        node = node.children.setdefault(letter, MarkedNode())
    node.is_word = True


def search_marked(root, word):
    node = root
    for letter in word:
        if letter not in node.children:
            return False
        node = node.children[letter]
    return node.is_word


unmarked = UnmarkedNode()
insert_unmarked(unmarked, "sung")
marked = MarkedNode()
insert_marked(marked, "sung")
for word in ["sung", "sun", "s", "sing"]:
    print(f"{word}: without the mark {search_unmarked(unmarked, word)}, with the mark {search_marked(marked, word)}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

sung: without the mark True, with the mark True
sun: without the mark True, with the mark False
s: without the mark True, with the mark False
sing: without the mark False, with the mark False

The fix is a boolean on every node, false by default, set to true on the last node of each inserted word, and read by the search after the walk. A count of the words ending at the node does the same job and also handles a word inserted twice.

To spot the mistake, look at what the search returns after its loop. If it returns true without reading a field of the node it reached, it is a prefix check under a search's name. Test it by inserting one long word and searching for its first letter.

On the Data Structures cheatsheet

← → move through sections and cards