Trie (Prefix Tree) (C)
Topics: data structures, strings, prefix trees
Problem
Implement a trie (prefix tree) over lowercase words, with nodes drawn from a
caller-provided pool (bump-allocated, no malloc). Support exact-word membership and
prefix queries.
#define TRIE_ALPHA 26
typedef struct TrieNode { struct TrieNode *children[TRIE_ALPHA]; bool end; } TrieNode;
typedef struct { TrieNode *pool; size_t cap; size_t used; TrieNode *root; } Trie;
void trie_init(Trie *t, TrieNode *storage, size_t cap);
bool trie_insert(Trie *t, const char *word); // false if non a-z, or pool full
bool trie_contains(const Trie *t, const char *word);
bool trie_starts_with(const Trie *t, const char *prefix);
Key concepts
- Each node is a fork of 26 letters. A word is a path from the root, one node per
character, following the
children[c] slot for each letter c. Insert creates
missing nodes from the pool along the way.
end distinguishes a word from a prefix. card and car share a path, so you
cannot tell "is this a word" from "does this path exist." Mark the final node of an
inserted word with end = true. Then trie_contains checks the path exists and
ends on a word; trie_starts_with only checks the path exists.- Cost is per-character. Lookups touch one node per character regardless of how
many words are stored, which is what makes tries great for autocomplete, routing
tables, and dictionaries.
- No allocation. Nodes come from the caller's
pool by bumping used; insert
fails gracefully when the pool runs out.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/trie && /tmp/trie
Sign in to submit your solution.