Trie (Prefix Tree) Implementation in C

A Trie, also known as a prefix tree, is a tree data structure used for storing a dynamic set of strings, where the keys are usually strings. Tries are particularly useful for performing quick lookups, such as autocomplete and spell checking, by leveraging the common prefixes of the stored strings.

Program Structure

This implementation of a Trie in C will include the following components:

1. Struct definitions for the Trie node and the Trie itself.
2. Functions to insert words into the Trie.
3. Functions to search for a word in the Trie.
4. Functions to check if there are any words in the Trie that start with a given prefix.
5. A main function to demonstrate the usage of the Trie for word insertion and lookup.

Code Implementation

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

#define ALPHABET_SIZE 26

// Trie node structure
typedef struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    bool isEndOfWord;
} TrieNode;

// Function to create a new Trie node
TrieNode* createNode() {
    TrieNode *newNode = (TrieNode*)malloc(sizeof(TrieNode));
    newNode->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) { newNode->children[i] = NULL;
    }
    return newNode;
}

// Function to insert a word into the Trie
void insert(TrieNode *root, const char *word) {
    TrieNode *node = root;
    while (*word) {
        int index = *word - 'a';
        if (node->children[index] == NULL) {
            node->children[index] = createNode();
        }
        node = node->children[index];
        word++;
    }
    node->isEndOfWord = true;
}

// Function to search for a word in the Trie
bool search(TrieNode *root, const char *word) {
    TrieNode *node = root;
    while (*word) {
        int index = *word - 'a';
        if (node->children[index] == NULL) {
            return false;
        }
        node = node->children[index];
        word++;
    }
    return node != NULL && node->isEndOfWord;
}

// Function to check if there is any word in the Trie that starts with the given prefix
bool startsWith(TrieNode *root, const char *prefix) {
    TrieNode *node = root;
    while (*prefix) {
        int index = *prefix - 'a';
        if (node->children[index] == NULL) {
            return false;
        }
        node = node->children[index];
        prefix++;
    }
    return true;
}

// Main function to demonstrate the usage of the Trie
int main() {
    TrieNode *root = createNode();

    // Insert words into the Trie
    insert(root, "hello");
    insert(root, "hell");
    insert(root, "heaven");
    insert(root, "heavy");

    // Search for words in the Trie
    printf("Search for 'hello': %s\n", search(root, "hello") ? "Found" : "Not Found");
    printf("Search for 'heaven': %s\n", search(root, "heaven") ? "Found" : "Not Found");
    printf("Search for 'hell': %s\n", search(root, "hell") ? "Found" : "Not Found");
    printf("Search for 'he': %s\n", search(root, "he") ? "Found" : "Not Found");

    // Check if any word starts with a given prefix
    printf("Starts with 'he': %s\n", startsWith(root, "he") ? "Yes" : "No");
    printf("Starts with 'hea': %s\n", startsWith(root, "hea") ? "Yes" : "No");
    printf("Starts with 'hel': %s\n", startsWith(root, "hel") ? "Yes" : "No");
    printf("Starts with 'ho': %s\n", startsWith(root, "ho") ? "Yes" : "No");

    return 0;
}

Explanation

The program implements a Trie (prefix tree) in C, which is a data structure commonly used to store a dynamic set of strings. The Trie allows for efficient retrieval of strings, especially when searching for strings with a common prefix.

The key components of this implementation are as follows:

The TrieNode struct represents a node in the Trie. Each node has an array of pointers to its children, representing the 26 lowercase English letters (a-z). Additionally, each node has a boolean flag isEndOfWord to indicate whether the node marks the end of a valid word.

The createNode() function creates and initializes a new Trie node, setting all its child pointers to NULL and isEndOfWord to false.

The insert() function inserts a word into the Trie. It traverses the Trie from the root, creating new nodes as necessary for each character in the word. When the end of the word is reached, it sets the isEndOfWord flag to true at the corresponding node.

The search() function searches for a word in the Trie. It traverses the Trie according to the characters of the word and returns true if the word exists in the Trie (i.e., if the final node reached is marked as the end of a word), otherwise it returns false.

The startsWith() function checks if there is any word in the Trie that starts with a given prefix. It returns true if the prefix exists in the Trie, otherwise it returns false.

In the main() function, we demonstrate the Trie’s functionality by inserting several words into the Trie, searching for specific words, and checking if any words start with certain prefixes.

This implementation of a Trie is efficient and can handle large sets of strings, making it ideal for applications like autocomplete, spell checking, and prefix-based searches.