Trie: count words with a prefix

Challenge

Build a lowercase-ASCII trie supporting:

typedef struct trie trie_t;
trie_t *trie_create(void);
void    trie_insert(trie_t *t, const char *word);
int     trie_count_prefix(trie_t *t, const char *prefix);
void    trie_destroy(trie_t *t);

trie_count_prefix returns the number of inserted words that start with prefix.

Why this matters

Tries underlie autocomplete, IP routing tables (radix tries), spell checkers, and the IPv4 BGP table compression in every internet router. Building one teaches recursive pointer structures.

Input format

Lowercase ASCII words, length <= 32. Up to 1000 words.

Output format

Count as int.

Constraints

Insert and count_prefix both O(len). No malloc in count_prefix.

Starter code

typedef struct trie trie_t;
trie_t *trie_create(void);
void    trie_insert(trie_t *t, const char *word);
int     trie_count_prefix(trie_t *t, const char *prefix);
void    trie_destroy(trie_t *t);

Common mistakes

Forgetting to bump the prefix counter on every node along the insert path; not initializing children to NULL (calloc helps); leaking allocations on destroy.

Edge cases to handle

Empty prefix returns total inserted. Prefix longer than any word returns 0.

Complexity

O(len) per op. Memory O(total chars * 26 pointer slots) — heavier than a hash map but cache-friendly for prefix scans.

Background lessons

• Recursion — base case + smaller subproblem