Trie in C: solved exercise

Trie in C: solved exercise

If you searched for a solved trie in C, here is the dynamic-allocation implementation covering insertion, exact search, and prefix search. A trie (prefix tree or digital tree) stores strings by sharing characters, enabling O(m) lookups — where m is the key length — regardless of how many strings the structure holds.

Problem statement

Implement a trie for the lowercase alphabet supporting:

1. trie_insert(root, word): inserts a word.
2. trie_search(root, word): returns 1 if the exact word exists.
3. trie_prefix(root, prefix): returns 1 if any word starts with the prefix.

Insert ["house", "hard", "heart", "dog", "dot"] and test several lookups.

C solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHA 26   /* lowercase a-z only */

typedef struct Node {
    struct Node *children[ALPHA];
    int end_of_word;   /* 1 if a word ends here */
} Node;

static Node *new_node(void) {
    Node *n = calloc(1, sizeof(Node));  /* calloc zeroes all fields */
    return n;
}

void trie_insert(Node *root, const char *word) {
    Node *cur = root;
    for (int i = 0; word[i]; i++) {
        int idx = word[i] - 'a';
        if (!cur->children[idx]) cur->children[idx] = new_node();
        cur = cur->children[idx];
    }
    cur->end_of_word = 1;
}

static Node *trie_path(Node *root, const char *s) {
    Node *cur = root;
    for (int i = 0; s[i]; i++) {
        int idx = s[i] - 'a';
        if (!cur->children[idx]) return NULL;
        cur = cur->children[idx];
    }
    return cur;
}

int trie_search(Node *root, const char *word) {
    Node *n = trie_path(root, word);
    return n && n->end_of_word;
}

int trie_prefix(Node *root, const char *prefix) {
    return trie_path(root, prefix) != NULL;
}

void trie_free(Node *n) {
    if (!n) return;
    for (int i = 0; i < ALPHA; i++) trie_free(n->children[i]);
    free(n);
}

int main(void) {
    Node *root = new_node();
    const char *words[] = {"house", "hard", "heart", "dog", "dot"};

    for (int i = 0; i < 5; i++) trie_insert(root, words[i]);

    /* Exact searches */
    const char *searches[] = {"house", "har", "heart", "do", "dot", "dogs"};
    for (int i = 0; i < 6; i++)
        printf("search(\"%s\") = %d\n", searches[i], trie_search(root, searches[i]));

    printf("\n");

    /* Prefix searches */
    const char *prefixes[] = {"har", "he", "do", "xyz", "h"};
    for (int i = 0; i < 5; i++)
        printf("prefix(\"%s\") = %d\n", prefixes[i], trie_prefix(root, prefixes[i]));

    trie_free(root);
    return 0;
}

Expected output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

search("house") = 1
search("har") = 0
search("heart") = 1
search("do") = 0
search("dot") = 1
search("dogs") = 0

prefix("har") = 1
prefix("he") = 1
prefix("do") = 1
prefix("xyz") = 0
prefix("h") = 1

Common mistakes

• Confusing exact search with prefix search: trie_search returns 1 only if end_of_word is set at the final node; trie_prefix only checks that the path exists.
• Not using calloc or not initializing child pointers to NULL: garbage pointer values make the if (!cur->children[idx]) checks incorrect.
• Not handling characters outside the supported alphabet: an uppercase 'A' gives a negative index and corrupts memory. Input must be validated.
• Not freeing the trie: each node is a separate malloc/calloc; all must be freed by traversing in postorder.

Practical use

Tries are used in autocomplete (search engines, IDEs), spell checking, data compression (LZW), IP routing with CIDR prefixes, and dictionary implementations with prefix-based lookups.

Recommended next exercise

• Deque in C: solved exercise
• Binary tree in C: solved exercise
• Min-heap in C: solved exercise
• All C exercises

Guided practice and full book

If you want a complete path with progressive difficulty:

• Programming in C in 100 Solved Exercises
• View on Amazon (included in Kindle Unlimited)

FAQ

How much memory does a trie consume?

Each node stores 26 pointers (for the a-z alphabet), consuming 26 × 8 = 208 bytes on 64-bit systems plus the end_of_word field. For small vocabularies this can be wasteful; the alternative is a compact trie (Patricia/Radix trie) that compresses paths with no branching.

Why is a trie faster than a hash table for prefix lookups?

A hash table requires searching each key individually to check whether it starts with a given prefix. A trie solves this in O(m) without traversing the whole structure: just follow the prefix path and verify that at least one descendant exists.

Can a trie be used for Unicode strings?

Yes, but the children array size must grow (or use a child→node map as a hash table or BST) to cover all possible code points. The most practical Unicode trie uses a hash map at each node.