Insert, exact search, and prefix search

What is a trie?

A trie, pronounced “try,” is a tree for storing words or other sequences by their prefixes. Each edge advances by one character. Words with the same beginning share a path. A terminal marker records where a complete word ends, since reaching a prefix does not mean that prefix is a stored word.

Example: The words "car" and "cat" share the path c → a. They then branch to r and t, each marked as the end of a word.

Helpful before this chapter

If these ideas are new, begin with:

Strings Hash maps and sets Binary trees

Understand the idea

Insertion follows or creates each edge, then marks the final node. Exact search requires a terminal; prefix search only requires a path. Deletion must preserve shared prefixes and other terminal words.

Work through an example

Inserting car after cat reuses c and a, creates r, and marks it. Deleting cat can remove t but not the shared ca path needed for car.

Time and space complexity

O(L) expected insert/search; worst node count added per word L.

Why it works

All inserted words retain complete terminal paths after each update.

Common mistakes

Returning bool(node) fails for an empty nonterminal dictionary.
Removing a whole shared path deletes other words.

Chapter lab · Python implementation

A trie shares common prefixes rather than repeatedly storing each complete word path. Edges consume characters; a terminal marker distinguishes a complete word from merely a prefix. Our lab inserts cat, car, and dog, then supports exact, prefix, and dot-wildcard matching over code points.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

class Trie:
    def __init__(self): self.root={}
    def insert(self,word):
        node=self.root
        for char in word: node=node.setdefault(char,{})
        node[None]=True
    def locate(self,prefix):
        node=self.root
        for char in prefix:
            if char not in node: return None
            node=node[char]
        return node
    def contains(self,word):
        node=self.locate(word)
        return node is not None and None in node
    def starts_with(self,prefix):
        return self.locate(prefix) is not None
    def matches(self,pattern):
        def visit(node,i):
            if i==len(pattern): return None in node
            char=pattern[i]
            if char=='.':
                return any(visit(child,i+1) for key,child in node.items() if key is not None)
            return char in node and visit(node[char],i+1)
        return visit(self.root,0)

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

t=Trie()
for word in ['cat','car','dog']: t.insert(word)
assert t.contains('cat') and not t.contains('ca')
assert t.starts_with('ca') and not t.starts_with('z')
assert t.matches('c.t') and not t.matches('c..s')
t.insert(''); assert t.contains('')

CHECK YOUR UNDERSTANDING