Tries

Use a trie when you need words sharing a prefix, such as all commands beginning with “ca”. It shares the work of reading that prefix.

Follow characters instead of comparing whole keys

Words: car, cart, cat

(root)
  c
  |
  a
 / \
r*  t*
|
t*

* marks a complete word

Every edge consumes one character. A node represents the prefix on the path from the root. A terminal marker says whether that prefix is also a complete stored word.

Lookup “car” follows c, a, r and checks the terminal marker. Prefix lookup “ca” follows c, a and succeeds even though “ca” is not a complete word. Lookup “can” fails when the n edge is missing.

Trace insertion and deletion

Insert “care”: reuse c, a, r; add an e child; mark e terminal. Keep r terminal because “car” remains a word.

Delete “car”: clear r's terminal marker. Keep r and its descendants because “cart” and “care” still need that path. Delete “care” next: remove the now-unused e leaf. Prune a node only when it is nonterminal and has no children.

That is the invariant: paths encode prefixes, and terminal markers encode membership independently of children. The empty word, if allowed, uses a terminal marker at the root.

Compare with a hash set

Let L be the word length and S the total length of all inserted words. Insertion, exact lookup, and deletion take O(L), assuming constant-time child lookup. Memory is O(S) in the worst case because each new character may need a node.

A fixed child array gives direct lookup but reserves space for the whole alphabet at each node. Child hash maps store only present edges with expected constant-time lookup. Ordered child maps cost more per step but support character order directly.

A hash set is often smaller and simpler for exact membership alone. Hashing a new word also reads its characters. A trie earns its overhead when prefix traversal matters. A sorted array of strings can also locate a prefix range using binary search, with comparison costs depending on string length.

Finding the prefix node takes O(L). Listing every matching word additionally visits the matching subtree and writes the output. It cannot take O(L) regardless of the number of matches. Child iteration order determines output order.

Predict and modify

1. Does inserting “car” twice require two terminal markers?
2. How would you count duplicate words?
3. Add a method that lists words under a prefix.

class Node:
    def __init__(self):
        self.children = {}
        self.terminal = False


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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = Node()
            node = node.children[char]
        node.terminal = True

    def walk(self, text):
        node = self.root
        for char in text:
            node = node.children.get(char)
            if node is None:
                return None
        return node

    def contains(self, word):
        node = self.walk(word)
        return node is not None and node.terminal

    def starts_with(self, prefix):
        return self.walk(prefix) is not None

    def delete(self, word):
        node = self.root
        path = []
        for char in word:
            child = node.children.get(char)
            if child is None:
                return False
            path.append((node, char))
            node = child
        if not node.terminal:
            return False
        node.terminal = False
        for parent, char in reversed(path):
            child = parent.children[char]
            if child.terminal or child.children:
                break
            del parent.children[char]
        return True


trie = Trie()
for word in ["car", "cart", "cat", "care"]:
    trie.insert(word)
assert trie.starts_with("ca") and not trie.contains("ca")
assert trie.delete("car") and not trie.contains("car")
assert trie.contains("cart") and trie.contains("care")
assert trie.delete("care") and trie.walk("care") is None
assert not trie.delete("can")
trie.insert("")
assert trie.contains("") and trie.delete("")

Apply prefix operations in Implement Trie.

Next: Disjoint set union.