Trie: count words with a prefix

Challenge

Build a trie that can count how many stored words share a given prefix.

Task

Implement a lowercase-ASCII trie with the following API. trie_count_prefix returns the number of inserted words that begin with prefix.

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);

Input

• Words and prefixes are lowercase ASCII ('a'..'z'), length <= 32. Up to 1000 words inserted.

Output

trie_count_prefix returns an int: the number of inserted words starting with prefix.

Example

insert "apple", "app", "apricot", "banana"
count_prefix("app")   ->   2    ("apple", "app")
count_prefix("ap")    ->   3    ("apple", "app", "apricot")
count_prefix("b")     ->   1    ("banana")
count_prefix("z")     ->   0
count_prefix("")      ->   4    (every word matches the empty prefix)

Edge cases

• The empty prefix matches all inserted words.
• A prefix that no word starts with returns 0.

Rules

• Insert and count_prefix are both O(len). Do not allocate inside count_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/prefixes, length <= 32; up to 1000 words.

Output format

int: number of inserted words starting with the given prefix.

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