Data structures in Python

Trie Lab

A trie, or prefix tree, stores words one letter per edge, so words that start the same share the same path. Step through insert, search, prefix lookup, wildcard matching and delete, and watch the walk down the tree one line of Python at a time.

Why a trie?

words = ["car", "card", "care", "cat", "dog", "do"]

"card" in set(words)   # fast, but only whole words
# "which words start with 'ca'?"
[w for w in words if w.startswith("ca")]  # checks all n

A trie stores each shared prefix once: "car", "card", "care" and "cat" all hang off the same c → a path. A lookup follows one edge per letter, so it costs O(L) for a word of length L, whether the trie holds six words or six million. And "every word starting with ca" is just everything below one node.

A node is a dict and a flag

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False  # does a word stop here?

class Trie:
    def __init__(self):
        self.root = TrieNode()

A node does not store its own letter. The letter is the key its parent files it under, which is why the drawing puts letters on the edges. The root is an empty node that every word starts from.

Why `is_end` is needed

trie.insert("card")
trie.search("car")   # path c-a-r exists...
                     # ...but no word ends there: False
trie.insert("car")   # creates no nodes at all,
                     # only sets is_end = True

"car" lies on the path to "card". The nodes alone cannot say whether "car" was inserted or is only a prefix. is_end marks the nodes where a real word stops; the lab draws them with a double ring and the word beside them.

Children: dict or 26-slot list

# dict: only the letters that exist
self.children = {}
child = self.children.get(ch)

# list: one slot per letter a-z
self.children = [None] * 26
child = self.children[ord(ch) - ord("a")]

A dict holds only the letters that exist and works for any alphabet, which suits Python and sparse tries. A list of 26 gives a fixed index with no hashing and children already in a–z order, but pays 26 slots per node even when 25 are None. This lab uses the dict.

a nodeis_end = True: a word stops herewhere node is nowpath from the rootdead end: tried and faileda child that is not therefound / collected

Tip: the ← and → keys step too. Every operation except Insert and Build starts from the same six words: car, card, care, cat, dog, do.

The word matcher: "." means any one letter

Here "word matcher" means wildcard search, as in LeetCode 211 (Add and Search Word): match("c.r") is True if some stored word has exactly three letters, a c, any letter, then an r.

A plain letter leaves exactly one child to follow, so it behaves like search. A . could be any child, so dfs tries them one by one. If a child's call returns False, that branch is a dead end: the call returns, its frame leaves the stack, and the loop moves on to the next child. That return-and-try-the-next is backtracking. The first branch that reaches the end of the pattern on a node with is_end = True makes every waiting call return True at once.

The length check comes for free: a branch that runs out of pattern on a node that is not a word end fails, and a branch that runs out of tree before the pattern ends fails too. Run .o to see a dead end before the hit, or d.t to watch every branch fail.

How much it costs

Insert, search, starts_with: O(L)

Each does one dict lookup per letter and nothing else, so the work is the length of the word, L. The number of stored words, n, never appears. A hash set also checks a word in O(L) on average, since hashing a string reads every character, but it cannot answer prefix questions without scanning all n words.

Word matcher: O(26^k · L) worst case

Each . can fan out to as many as 26 children, and every one of those branches can meet more dots further down. With k dots that is up to 26^k branches, each walking up to L levels. In practice two things keep it far smaller: branches die as soon as a letter is missing, and every node is visited at most once per call, because a node at depth d is only ever reached with i = d. So the work is also capped by the number of nodes in the trie.

Space: one node per distinct prefix

The worst case is the total number of letters across all words, when no prefixes are shared. Sharing brings it down; the six words in this lab have 19 letters but need only 9 nodes. Each node is an object with its own dict, though, which in CPython costs on the order of 100–200 bytes, so a trie of short words often uses more memory than a plain set of strings.

Autocomplete: O(L + size of the subtree)

def autocomplete(self, prefix):
    node = self.root
    for ch in prefix:          # O(len(prefix))
        if ch not in node.children:
            return []
        node = node.children[ch]
    words = []
    def collect(node, path):   # O(size of subtree)
        if node.is_end:
            words.append(path)
        for ch, child in node.children.items():
            collect(child, path + ch)
    collect(node, prefix)
    return words

Walking to the prefix costs O(L); collecting visits every node below it once. Words outside the prefix are never touched, which is the whole point.

When to use a trie, and when a set is enough

You need	Use	Why
Is this exact word stored?	set	O(L) average, less memory, one line of Python
Autocomplete / type-ahead	trie	walk to the prefix node, then collect its subtree
Does any word start with this prefix?	trie	starts_with is O(L); a set must scan every word
Wildcard patterns ("c.t")	trie	DFS prunes whole subtrees at the first missing letter
Word games (Boggle, word search grids)	trie	stop exploring a path as soon as no word has that prefix
Spell-check suggestions	trie	search nearby spellings while walking shared prefixes once
Longest common prefix of many words	trie	follow the root while there is exactly one child and no word end
Count words, sort them	list / sorted()	a trie gives sorted order only with ordered children

Common mistakes

Forgetting `is_end` in insert

def insert(self, word):
    node = self.root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
    # forgot: node.is_end = True

The nodes get built, so starts_with still works, but no node is ever marked as a word end. Every search returns False, even for the word you just inserted. Insert's last line is the one that records the word.

Search that returns True for a prefix

def search(self, word):
    node = self.root
    for ch in word:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return True   # search("ca") -> True

    return node.is_end

That is starts_with, not search. With "card" stored, the path c-a exists, so the buggy version claims "ca" is a word. Run Search with ca above to see is_end decide.

Special-casing "." at the last position

if ch == '.':
    if i == len(pattern) - 1:
        return len(node.children) > 0
# only "card" stored: match("ca.") -> True

if ch == '.':
    for child in node.children.values():
        if dfs(child, i + 1):   # the base case
            return True         # checks is_end
    return False

Having a child is not the same as having a word: the child must be a word end. Let the dot recurse like every other position, and the i == len(pattern) base case checks is_end for you. Try ca. in the matcher.

Creating nodes during search

def search(self, word):
    node = self.root
    for ch in word:
        node = node.children.setdefault(ch, TrieNode())
    return node.is_end
# search("cab") adds 'b'; later
# starts_with("cab") -> True

        if ch not in node.children:
            return False   # read only, never build

setdefault (or a defaultdict) quietly builds the path it was asked about. search still says False, but the junk nodes make starts_with lie afterwards and the trie grows with every miss. Lookups must only read.

Cost of each operation

Operation	Time	Extra space	Notes
insert(word)	O(L)	O(L) new nodes at most	reuses every node of the shared prefix
search(word)	O(L)	O(1)	answer is the last node's is_end
starts_with(prefix)	O(L)	O(1)	True as soon as the path exists
match(pattern) with k dots	O(26^k · L) worst	O(L) call stack	also at most one visit per node
autocomplete(prefix)	O(L + m)	O(depth) stack + output	m = nodes under the prefix node
delete(word)	O(L)	O(L) call stack	unmark is_end, prune childless non-word nodes
Build from n words	O(total letters)	O(total letters) worst	shared prefixes are stored once

L is the length of the word, prefix or pattern. With a 26-slot list instead of a dict, each step is a list index instead of a hash lookup, and each node always costs 26 slots.