Trie — KLAR

Phase 1f(x)

The Mathematics

Prefix trees, shared prefixes, and search complexity

Prefix Tree Definition

A trie (prefix tree) is a rooted tree where each edge is labeled with a character from an alphabet $\Sigma$ . Each node represents a prefix:

\text{node}(v) \;\leftrightarrow\; \text{prefix } w[0..k]

Words sharing a common prefix share the same path from the root. End-of-word is marked with a boolean flag at the terminal node.

Shared Prefixes

The key advantage: words with common prefixes share nodes. For words $w_1$ and $w_2$ , the shared prefix path has length:

\text{lcp}(w_1, w_2) = \max\{k : w_1[0..k] = w_2[0..k]\}

This saves space compared to storing each word independently. For example, "cat", "car", "card" share the prefix "ca".

Complexity Analysis

For a word of length $m$ :

\text{insert}(w) = O(m), \quad \text{search}(w) = O(m)

Both operations are independent of the total number of stored words $n$ . Space in the worst case:

O\!\left(\sum_{i=1}^{n} |w_i| \cdot |\Sigma|\right)

Trie vs. Hash Table

Hash tables offer $O(m)$ average lookup but don't support prefix queries. Tries enable prefix search, autocomplete, and lexicographic ordering — all in $O(m)$ time.

Phase 2▶

See It Work

Building a trie from words: cat, car, card, do, dog

Active Path End of Word

T = (\{\text{root}\},\; \emptyset)

Step 1 of 6

Initialize: empty trie with just the root node.

Phase 3</>

The Code

Bridge from prefix tree operations to Python implementation

Mathematical Formulation

\text{children}: \Sigma \to \text{Node}

Each node maps characters to child nodes (branching factor up to |Σ|)

\text{is\_end} \in \{\text{true}, \text{false}\}

Boolean flag marking whether this node completes a word

\text{root} = \text{TrieNode}()

Trie starts with an empty root (represents empty prefix "")

\text{traverse}: w[0], w[1], \ldots, w[m-1]

Insert processes each character of the word sequentially

c \notin \text{children} \Rightarrow \text{create node}

Create a new node if the character path doesn't exist yet

\text{is\_end}(w[m-1]) = \text{true}

After inserting all characters, mark the last node as end-of-word

\text{search}: O(m) \text{ where } m = |w|

Search is O(m) — independent of how many words are stored

Python Implementation

class TrieNode:
    def __init__(self):
        self.children = {}             # Map: char -> TrieNode
        self.is_end = False            # Marks end of a word

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

    def insert(self, word):
        node = self.root               # Start at root
        for char in word:              # Traverse each character
            if char not in node.children:
                node.children[char] = TrieNode()  # Create if missing
            node = node.children[char] # Move to child
        node.is_end = True             # Mark end of word

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False           # Character not found
            node = node.children[char]
        return node.is_end             # True only if full word exists

Trie (Prefix Tree)