Trie (Prefix Tree)

What is Trie

Trie (from retrieval) is a search tree where the key is not stored explicitly in the node, but is defined by the path from the root to the node. Each node represents a single character, and the path from the root to a leaf forms a word.

It was invented by Edward Fredkin in 1960.

Key Properties

Node Structure

┌──────────────────────────────────┐
│  children[0..A-1]                │  ← A pointers (A = alphabet size)
│  is_end: bool                    │  ← end-of-word marker
│  value: any  (optional)          │  ← payload
└──────────────────────────────────┘

Visualization

Words inserted: cat, car, card, care, bat, bad

✓ = is_end = true — this is where a word ends.

Basic Operations

➕ Insertion — O(m)

Inserting "care":
  root → c → a → r → e (is_end = true)

If a node already exists, we simply proceed to the next character.
If not, we create a new node.

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

🔍 Search — O(m)

Search for "car":
  root → c ✓ → a ✓ → r ✓ → is_end? → True ✓

Search for "ca":
  root → c ✓ → a ✓ → is_end? → False ✗ (exists as a prefix, but not a word)

Search for "cat":
  root → c ✓ → a ✓ → t ✓ → is_end? → True ✓

def search(root, word):
    node = 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 it's a full word

🔍 Prefix Search — O(m)

def starts_with(root, prefix):
    node = root
    for char in prefix:
        if char not in node.children:
            return False
        node = node.children[char]
    return True   # prefix exists (even if no corresponding word does)

➖ Deletion — O(m)

Recursive traversal: remove a node only if it is not an ancestor of another word.

Deleting "car" (but "card", "care" remain):
  → do NOT delete node 'r' — it has children (d, e)
  → just reset is_end = false

Operation Complexity

Pros and Cons