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

root points to trie node; prefix is a null-terminated lowercase ASCII string.

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

Dereferencing NULL child pointer when prefix path does not exist in trie.

Edge cases to handle

Empty prefix, prefix not in trie, prefix matching entire word.

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