{"id":815,"date":"2024-10-14T14:28:54","date_gmt":"2024-10-14T08:58:54","guid":{"rendered":"https:\/\/codexplained.in\/?p=815"},"modified":"2025-11-24T15:42:10","modified_gmt":"2025-11-24T10:12:10","slug":"implementation-of-tire-data-structure","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=815","title":{"rendered":"Implementation of Tire Data Structure"},"content":{"rendered":"\n

Key Features of a Trie<\/h3>\n\n\n\n
    \n
  1. Node Structure<\/strong>: Each node in the Trie contains an array of pointers (one for each character) and a boolean flag to indicate if the node marks the end of a valid word.<\/li>\n\n\n\n
  2. Insertion<\/strong>: To insert a word, you traverse down the Trie, creating new nodes as needed for each character.<\/li>\n\n\n\n
  3. Search<\/strong>: To search for a word, you follow the path down the Trie according to the characters in the word.<\/li>\n\n\n\n
  4. Prefix Search<\/strong>: You can also search for all words that start with a given prefix.<\/li>\n<\/ol>\n\n\n\n

    C Program to Implement a Trie Data Structure<\/h3>\n\n\n
    \n#include <stdio.h>\n#include <stdlib.h>\n#include <stdbool.h>\n#include <string.h>\n\n#define ALPHABET_SIZE 26 \/\/ Assuming only lowercase letters a-z\n#define MAX_WORD_LENGTH 100 \/\/ Maximum length for a word\n\n\/\/ Trie node structure\nstruct TrieNode {\n    struct TrieNode* children[ALPHABET_SIZE];\n    bool isEndOfWord; \/\/ True if the node represents the end of a word\n};\n\n\/\/ Function to create a new Trie node\nstruct TrieNode* createNode() {\n    struct TrieNode* newNode = (struct TrieNode*)malloc(sizeof(struct TrieNode));\n    newNode->isEndOfWord = false;\n    for (int i = 0; i < ALPHABET_SIZE; i++) {\n        newNode->children[i] = NULL; \/\/ Initialize all children to NULL\n    }\n    return newNode;\n}\n\n\/\/ Function to insert a word into the Trie\nvoid insert(struct TrieNode* root, const char* word) {\n    struct TrieNode* currentNode = root;\n\n    while (*word) {\n        int index = *word - 'a'; \/\/ Calculate index for the current character\n        if (!currentNode->children[index]) {\n            currentNode->children[index] = createNode(); \/\/ Create new node if it doesn't exist\n        }\n        currentNode = currentNode->children[index]; \/\/ Move to the next node\n        word++; \/\/ Move to the next character\n    }\n    currentNode->isEndOfWord = true; \/\/ Mark the end of the word\n}\n\n\/\/ Function to search for a word in the Trie\nbool search(struct TrieNode* root, const char* word) {\n    struct TrieNode* currentNode = root;\n\n    while (*word) {\n        int index = *word - 'a';\n        if (!currentNode->children[index]) {\n            return false; \/\/ If the character doesn't exist, word not found\n        }\n        currentNode = currentNode->children[index];\n        word++;\n    }\n    return currentNode->isEndOfWord; \/\/ Return true if it's the end of a valid word\n}\n\n\/\/ Function to check if there is any word in the Trie that starts with the given prefix\nbool startsWith(struct TrieNode* root, const char* prefix) {\n    struct TrieNode* currentNode = root;\n\n    while (*prefix) {\n        int index = *prefix - 'a';\n        if (!currentNode->children[index]) {\n            return false; \/\/ If the prefix doesn't exist, return false\n        }\n        currentNode = currentNode->children[index];\n        prefix++;\n    }\n    return true; \/\/ Prefix found\n}\n\n\/\/ Main function to demonstrate the Trie operations\nint main() {\n    struct TrieNode* root = createNode(); \/\/ Create the root node\n\n    int choice;\n    char word[MAX_WORD_LENGTH];\n\n    \/\/ Interactive menu for Trie operations\n    while (1) {\n        printf("1. Insert a word\\n");\n        printf("2. Search for a word\\n");\n        printf("3. Check for a prefix\\n");\n        printf("4. Exit\\n");\n        printf("Enter your choice: ");\n        scanf("%d", &choice);\n        getchar(); \/\/ Consume newline character\n\n        switch (choice) {\n            case 1:\n                printf("Enter a word to insert: ");\n                fgets(word, sizeof(word), stdin);\n                word[strcspn(word, "\\n")] = '\\0'; \/\/ Remove newline character\n                insert(root, word);\n                printf("Inserted: %s\\n", word);\n                break;\n            case 2:\n                printf("Enter a word to search: ");\n                fgets(word, sizeof(word), stdin);\n                word[strcspn(word, "\\n")] = '\\0'; \/\/ Remove newline character\n                printf("Searching for '%s': %s\\n", word, search(root, word) ? "Found" : "Not Found");\n                break;\n            case 3:\n                printf("Enter a prefix to check: ");\n                fgets(word, sizeof(word), stdin);\n                word[strcspn(word, "\\n")] = '\\0'; \/\/ Remove newline character\n                printf("Prefix '%s': %s\\n", word, startsWith(root, word) ? "Exists" : "Does not exist");\n                break;\n            case 4:\n                printf("Exiting...\\n");\n                free(root); \/\/ Free the allocated memory\n                return 0;\n            default:\n                printf("Invalid choice. Please try again.\\n");\n        }\n    }\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
    Explanation of the Updated Code<\/h3>\n\n\n\n
      \n
    1. User Interaction<\/strong>:\n
        \n
      • The program now presents a simple menu for the user to choose from inserting a word, searching for a word, checking a prefix, or exiting.<\/li>\n\n\n\n
      • The user can input words and prefixes directly, making it more interactive.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Input Handling<\/strong>:\n
          \n
        • fgets<\/code> is used to read strings, allowing for spaces in input. The newline character is removed using strcspn<\/code> to ensure the strings are formatted correctly.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Dynamic Operations<\/strong>:\n
            \n
          • The Trie operations remain the same (insert, search, prefix checking), but now they respond to user inputs in real-time.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
            How to Run the Program<\/h3>\n\n\n\n
              \n
            1. Compile the code using a C compiler (e.g., gcc<\/code>):Copy codegcc trie.c -o trie<\/code><\/li>\n\n\n\n
            2. Run the compiled program:bashCopy code.\/trie<\/code><\/li>\n\n\n\n
            3. Follow the prompts to insert words, search for them, and check prefixes.<\/li>\n<\/ol>\n\n\n\n
              Sample Input and Output<\/h3>\n\n\n\n
              Here\u2019s how a sample interaction with the program might look:<\/p>\n\n\n\n
              mathematicaCopy code1. Insert a word\n2. Search for a word\n3. Check for a prefix\n4. Exit\nEnter your choice: 1\nEnter a word to insert: hello\nInserted: hello\n1. Insert a word\n2. Search for a word\n3. Check for a prefix\n4. Exit\nEnter your choice: 1\nEnter a word to insert: hi\nInserted: hi\n1. Insert a word\n2. Search for a word\n3. Check for a prefix\n4. Exit\nEnter your choice: 2\nEnter a word to search: hello\nSearching for 'hello': Found\n1. Insert a word\n2. Search for a word\n3. Check for a prefix\n4. Exit\nEnter your choice: 3\nEnter a prefix to check: he\nPrefix 'he': Exists\n1. Insert a word\n2. Search for a word\n3. Check for a prefix\n4. Exit\nEnter your choice: 4\nExiting...\n<\/code><\/pre>\n\n\n\n
              Conclusion<\/h3>\n\n\n\n
              This updated implementation of the Trie allows for dynamic interaction and showcases the functionalities effectively. You can test various words and prefixes, making it a practical tool for understanding how Tries work.<\/p>\n