A few years back, I was helping a colleague optimize a CLI tool that managed thousands of configuration keys for a network emulator. The tool had a "suggest" feature where you'd type a few letters, and it would list all matching keys. Initially, they just stored the keys in a giant sorted array and used binary search to find the range of matches. It worked fine for a hundred keys, but once the project scaled to ten thousand keys, the performance dipped, and the code for handling prefix ranges became a nightmare of pointer arithmetic and edge cases. I told them they were fighting the data structure. We swapped the array for a Trie, and suddenly the lookup time depended only on the length of the prefix the user typed, not the size of the entire configuration set. It was a night-and-day difference.

The Anatomy of a Prefix Node

At its core, a Trie (from "re-trie-val") isn't like a binary search tree where you compare values. Instead, each node represents a single character of a string. If you're storing lowercase English words, each node typically contains an array of 26 pointers—one for each possible next letter. I usually recommend using a fixed-size array for simplicity, though if you're dealing with the full UTF-8 spectrum, you'd probably want a hash map or a linked list at each node to save memory. You also need a way to mark the end of a word, because just because a path exists doesn't mean it represents a complete entry; it might just be a prefix for a longer word.

typedef struct TrieNode {
    struct TrieNode *children[26];
    bool isEndOfWord;
} TrieNode;

When you allocate this, remember that every single child pointer must be initialized to NULL. C won't do that for you, and chasing a random pointer in a Trie is a fast track to a segfault. I typically use calloc here to ensure the memory is zeroed out from the start.

Walking the Tree for Insertion and Search

Inserting a word is a matter of walking down the tree, character by character. For each character in your string, you calculate the index (e.g., str[i] - 'a'), check if a node exists at that index, and if not, create one. By the time you hit the null terminator of your string, you simply flip the isEndOfWord flag to true. Searching follows the exact same logic: you follow the pointers until you either hit a NULL (meaning the word doesn't exist) or you reach the end of your search string and find that isEndOfWord is true.

void insert(TrieNode *root, const char *key) {
    TrieNode *curr = root;
    while (*key) {
        int index = *key - 'a';
        if (!curr->children[index]) {
            curr->children[index] = calloc(1, sizeof(TrieNode));
        }
        curr = curr->children[index];
        key++;
    }
    curr->isEndOfWord = true;
}

This approach is incredibly powerful for prefix searches. If you want to find all words starting with "pre", you just navigate to the node representing 'e' and then perform a depth-first search (DFS) from that point downward to collect every possible completion. This is why Tries are the gold standard for autocomplete systems.

The Cleanup Headache

Here is where most developers stumble: memory management. Because a Trie is a tree of dynamically allocated nodes, you can't just free(root). You have to recursively traverse the entire structure and free the children before you free the parent. If you don't, you're leaking memory every time you tear down a Trie, which in a long-running server process is a catastrophic bug. I always write a dedicated freeTrie function that handles this post-order traversal—visiting all children before the current node.

📋 Practical Task

Exercise: Implementing a Command-Line Autocomplete Engine

Your task is to build a small-scale autocomplete engine using a Trie. You will need to implement the following functionality in C:

• A insert function that takes a TrieNode* and a string.
• A search function that returns true if a full word exists in the Trie.
• A startsWith function that returns true if any word in the Trie starts with the given prefix.
• A freeTrie function to properly clean up all allocated nodes to ensure zero memory leaks (test this with Valgrind if you have it).

Requirements:
Assume all input strings consist only of lowercase English letters ('a'-'z').
Your main function should insert the following words: "apple", "app", "apply", "ball", and "bat".
Verify that search("app") is true, search("appl") is false, and startsWith("app") is true.