Tries and Graphs

This chapter implements a trie (prefix tree) and the two fundamental graph representations (adjacency list and adjacency matrix).

Why This Matters

Tries give prefix-based lookup in O(key-length), powering autocomplete, IP routing, and dictionaries. Graphs model relationships and are the substrate for routing, dependency resolution, social networks, and compiler analyses.

Prerequisites

• c.ds.6 — binary trees.

Core Concept

Trie

A trie stores strings as paths from a root; each edge is a character. A node may be marked as "end of a word." Lookup/insert are O(L) where L is the key length, independent of the number of keys.

typedef struct TrieNode {
    struct TrieNode *children[26];  /* for a-z */
    _Bool is_end;
} TrieNode;

Graphs

A graph is vertices plus edges. Two common representations:

• Adjacency list: each vertex has a linked list (or array) of neighbors.

Space O(V + E), efficient for sparse graphs.

• Adjacency matrix: a V×V matrix; m[i][j] is 1 (or weight) if there is

an edge i→j. Space O(V²), efficient for dense graphs.

Examples

Trie insert/search (lowercase a-z)

#include <stdlib.h>

TrieNode *trie_new(void)
{
    TrieNode *n = calloc(1, sizeof *n);
    return n;
}

int trie_insert(TrieNode *root, const char *s)
{
    TrieNode *n = root;
    for (; *s; s++) {
        int i = *s - 'a';
        if (i < 0 || i >= 26) return -1;
        if (n->children[i] == NULL) {
            n->children[i] = trie_new();
            if (!n->children[i]) return -1;
        }
        n = n->children[i];
    }
    n->is_end = 1;
    return 0;
}

_Bool trie_search(TrieNode *root, const char *s)
{
    TrieNode *n = root;
    for (; *s; s++) {
        int i = *s - 'a';
        if (i < 0 || i >= 26 || !n->children[i]) return 0;
        n = n->children[i];
    }
    return n->is_end;
}

Adjacency list graph

typedef struct Edge {
    int to;
    struct Edge *next;
} Edge;

typedef struct {
    Edge **adj;   /* array of adjacency lists */
    int V;
} Graph;

How It Works

A trie shares prefixes, so common prefixes are stored once. Lookup walks the path character by character. An adjacency list stores neighbors per vertex; an adjacency matrix stores all pairs directly.

Variations

Compressed tries

Compress single-child paths to save space (radix/Patricia trees), used in routing tables.

Weighted and directed graphs

Edges may be directed/undirected and carry weights. Adjacency lists store weights in the edge; matrices store weights in the cell.

Common Mistakes

• Forgetting to mark is_end (word falsely reported absent).
• Indexing children without validating the character range.
• Confusing adjacency list vs. matrix trade-offs.
• Not freeing the entire trie/graph (leaks).

Undefined Behavior

• Out-of-bounds child index (e.g., non-'a'-'z' character). VERIFIED
• Dereferencing a NULL node.

Portability

• Plain C, fully portable. Fixed-size child arrays (e.g., 26) are simple but

ASCII/lowercase-specific; use 256 for full bytes or a dynamic map for Unicode.

Under the Hood

A trie trades memory for speed (many child pointers). A graph's adjacency list chases pointers (cache-unfriendly); the matrix is dense but gives O(1) edge checks.

Practical Usage

• Use tries for autocomplete, prefix matching, and string dictionaries.
• Use adjacency lists for sparse graphs (typical); matrices for dense graphs.

Exercises

1. Implement trie insert/search/delete and a prefix count function. 2. Implement an adjacency-list graph with add-edge and DFS/BFS traversal. 3. Implement an adjacency-matrix graph and compare memory for a sparse graph.

Deep Challenge

Implement a trie that counts the number of words with a given prefix, and explain how to extend it to return all completions. Then discuss the memory trade-offs of a 26-way vs. 256-way trie.

Related Concepts

• c.alg.3 — BFS/DFS/Dijkstra.
• c.alg.4 — string algorithms.
• c.ds.6 — trees.

References

• Standard data-structure literature.

Verification

• Trie and graph representation semantics. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Trie insert/search
• [ ] Prefix matching
• [ ] Adjacency list
• [ ] Adjacency matrix

Mastery levels