Tries

Definition

A trie (from retrieval) is a tree-shaped data structure where each node represents a single character of a key. Keys sharing a common prefix share the same path from the root.

• The root node is empty (represents the empty string)
• Each edge is labelled with a character from the alphabet
• Every path from root to a flagged node spells out a stored key
• No node stores the key itself — the key is implicit in the path
• Also called a prefix tree or digital tree

First described by Fredkin (1960) and de la Briandais (1959). Pronounced "try" to distinguish from "tree".

Basic structure

           (root)
          /   |   \
         c    d    t
         |    |   / \
         a    o  h   o
        / \   |  |   |
       r   t  g  e   p
       |
       s
     (cars) (cat) (dog) (the) (top)

Array-based node (fixed alphabet)

class TrieNode:
    def __init__(self):
        self.children = [None] * 26  # a-z
        self.is_end = False
        self.value = None            # optional

Hash-map-based node (variable alphabet)

class TrieNode:
    def __init__(self):
        self.children = {}           # char -> TrieNode
        self.is_end = False

Comparison

Algorithm

1. Start at the root node
2. For each character c in the key: if children[c] exists, move to that child; otherwise create a new node and move to it
3. Mark the final node as is_end_of_word = True

def insert(root, word):
    node = root
    for char in word:
        idx = ord(char) - ord('a')
        if node.children[idx] is None:
            node.children[idx] = TrieNode()
        node = node.children[idx]
    node.is_end = True

Inserting "cat", "car", "card"

After "cat":     After "car":
    (root)           (root)
      |                |
      c                c
      |                |
      a                a
      |               / \
      t*             t*   r*

After "card":
    (root)
      |
      c
      |
      a
     / \
    t*   r*
         |
         d*

Exact search

1. Start at the root
2. For each character c: if children[c] is None, return False; else move to that child
3. Return True only if is_end_of_word = True

def search(root, word):
    node = root
    for char in word:
        idx = ord(char) - ord('a')
        if node.children[idx] is None:
            return False
        node = node.children[idx]
    return node.is_end

Prefix check

def starts_with(root, prefix):
    node = root
    for char in prefix:
        idx = ord(char) - ord('a')
        if node.children[idx] is None:
            return False
        node = node.children[idx]
    return True  # path exists = prefix exists

Algorithm

1. Recursively traverse to the end of the key
2. Unmark is_end_of_word
3. On the way back up, delete nodes that are no longer end-of-word markers AND have no remaining children

def delete(root, word, depth=0):
    if root is None:
        return False
    if depth == len(word):
        if not root.is_end:
            return False
        root.is_end = False
        return not any(root.children)
    idx = ord(word[depth]) - ord('a')
    should_delete = delete(
        root.children[idx], word, depth + 1)
    if should_delete:
        root.children[idx] = None
        return (not root.is_end
                and not any(root.children))
    return False

Delete "cars" from {car, cars, cat}

Before:          After:
  c                c
  |                |
  a                a
 / \              / \
t*   r*          t*   r*
     |
     s*  <-- removed

Collecting all words with a given prefix

1. Navigate to the node representing the prefix
2. Run DFS from that node, collecting all paths to is_end nodes

def autocomplete(root, prefix):
    node = root
    for char in prefix:
        idx = ord(char) - ord('a')
        if node.children[idx] is None:
            return []
        node = node.children[idx]
    results = []
    _dfs(node, prefix, results)
    return results

def _dfs(node, current, results):
    if node.is_end:
        results.append(current)
    for i in range(26):
        if node.children[i]:
            _dfs(node.children[i],
                 current + chr(i + ord('a')),
                 results)

Example

Prefix "ca" -> navigate to 'a' under 'c'
DFS finds: "car", "card", "cars", "cat"

The problem with standard tries

Chains of single-child nodes waste memory:

Standard trie for
{"romane", "romanus", "romulus"}:

r -> o -> m -> a -> n -> e*
                       -> u -> s*
               -> u -> l -> u -> s*

Many single-child nodes.

Radix tree (compressed trie)

Merge single-child chains into edges with multi-character labels:

Radix tree:
       "rom"
      /     \
   "an"     "ulus"*
   /   \
  "e"*  "us"*

Patricia trie

Practical Algorithm To Retrieve Information Coded In Alphanumeric (Morrison, 1968). A radix tree where every internal node has at least two children.

Structure

Each node has three children:

• Left: characters less than current
• Middle: characters equal (continue down the key)
• Right: characters greater than current

Insert "cat", "cup", "bat":

         c
        /|\
       b  a  u
       |  |  |
       a  t* p*
       |
       t*

Comparison

Definition

A suffix trie for string S of length n is a trie containing all n suffixes of S.

Example: "banana$"

Suffixes: banana$, anana$, nana$, ana$, na$, a$, $

Insert all suffixes into a standard trie:

      (root)
    / | | | \ \  \
   b  a  n  $  ...
   |  |  |
   a  n  a
   |  |  |
   n  a  n
  ... ... ...

Properties

• Every substring of S is a prefix of some suffix — so substrings can be found by prefix search
• Substring search: O(m) — search the trie for the pattern
• Count occurrences: count leaves below the matching node
• Space: O(n2) — each suffix has O(n) characters

From suffix trie to suffix tree

Apply path compression (radix tree) to the suffix trie — merge single-child chains into edges labelled with substrings.

Suffix tree for "banana$":

         (root)
       /   |    \
     $   a       banana$
        / \
      $   na
         / \
        $  na$

Key properties

• Space: O(n) nodes and edges
• Construction: Ukkonen's algorithm — O(n) online
• Substring search: O(m) for pattern of length m
• Longest repeated substring: deepest internal node

Ukkonen's algorithm (1995)

• Builds suffix tree incrementally, left to right
• Three extension rules: leaf extension, new branch, do nothing
• Suffix links for amortised linear time
• Active point tracks position: (active_node, active_edge, active_length)

Definition

A generalised suffix tree (GST) stores the suffixes of multiple strings simultaneously. Each leaf is labelled with both a string index and suffix position.

Construction

1. Concatenate strings with unique sentinels: banana$1bandana$2
2. Build suffix tree on the concatenation
3. Mark each leaf with its originating string

Construction remains O(N) where N is the total length of all strings.

Applications

Binary trie

A trie over the alphabet {0, 1}. Keys are bit strings. Each level inspects one bit.

Insert 5 (101), 2 (010), 7 (111):

       (root)
      0/    \1
     (0)    (1)
    0/ \1  0/ \1
   ( ) ( ) (1) ( )
   |   |   |    |
  ... 2*  5*   7*

Crit-bit tree

Only branch at "critical bits" where keys differ — skip identical prefix bits. Minimal branching, fast lookups.

Applications

Motivation

Standard tries have poor cache locality — every character lookup follows a pointer to a different memory location.

Structure

• Internal nodes are standard trie nodes
• Leaf nodes are containers (sorted arrays, small hash maps) holding key suffixes
• When a container exceeds a threshold, it bursts into trie nodes

Burst trie:

     (root)
    /      \
   a        b
   |        |
 [pple,    [at, oy,
  rt,       us]*
  xe]*

* = container (sorted list)

Performance

Autocomplete

• Search engines: type "how to" — suggest completions ranked by popularity
• IDEs: type str. — list methods starting with that prefix
• Implementation: trie with frequency weights; top-k via priority queue

Weighted trie for autocomplete:

    (root)
      |
      c
      |
      a
     / \
    r    t  (freq: 500)
    |
   (freq: 300)
    |
    s  (freq: 100)

Spell checking

• Build a trie of dictionary words
• For a query, search within edit distance d: traverse the trie tracking insertions, deletions, substitutions (Levenshtein)
• Prune branches where accumulated distance exceeds d
• Much faster than checking edit distance against every word

IP routing — longest prefix match

Routers store rules as IP prefixes with varying lengths. For each packet, find the longest matching prefix.

Routing table:
  10.0.0.0/8     -> Gateway A
  10.1.0.0/16    -> Gateway B
  10.1.1.0/24    -> Gateway C

Packet to 10.1.1.42:
  Matches all three
  Longest prefix = /24 -> Gateway C

• Binary trie on IP bits: O(W) lookup (W = 32 for IPv4, 128 for IPv6)
• Multi-bit tries (LC-trie) inspect 4-8 bits per level
• Hardware TCAM achieves single-cycle lookup

T9 predictive text

Map phone keypad digits to letters: 2=abc, 3=def, ... Build a trie keyed on digit sequences.

Input: 4-3-5-5-6
Trie path: 4 -> 3 -> 5 -> 5 -> 6
Matches: "hello", "jello"

Other applications

Key takeaways

• A trie stores keys as paths — prefix sharing is the core advantage
• Insert, search, delete are O(m) — independent of stored key count
• Prefix search and autocomplete are native trie operations with no hash table equivalent
• Compressed tries (radix/Patricia) reduce space to O(n) nodes
• Suffix trees solve substring problems in linear time
• Ternary search tries balance memory and speed for large alphabets
• Bitwise tries power IP routing and integer data structures
• Burst tries improve cache locality via compact containers
• Choose tries for prefix ops and worst-case guarantees; hash tables for raw exact-match speed

Recommended reading