Autocomplete System with Trie in DSA C - Build from Scratch

Autocomplete System with Trie

📖 Scenario: Imagine you are building a simple autocomplete feature for a search box. When a user starts typing, the system suggests words that start with the typed letters. To do this efficiently, you will use a Trie data structure.

🎯 Goal: Build a Trie to store a list of words and implement a function to find all words in the Trie that start with a given prefix.

📋 What You'll Learn

Create a Trie node structure with children and end-of-word marker

Insert given words into the Trie

Implement a function to find all words starting with a given prefix

Print the list of autocomplete suggestions for the prefix

💡 Why This Matters

🌍 Real World

Autocomplete systems are used in search engines, text editors, and mobile keyboards to help users type faster by suggesting words based on what they start typing.

💼 Career

Understanding Tries and autocomplete logic is useful for software engineers working on search features, user interfaces, and performance optimization.

1

Create Trie Node Structure and Insert Words

Define a struct called TrieNode with an array children of size 26 for each letter and an isEndOfWord integer flag. Then create a function getNode() that returns a new TrieNode with all children set to NULL and isEndOfWord set to 0. Finally, create a function insert() that takes a TrieNode* root and a char* word and inserts the word into the Trie.

DSA C

# Define TrieNode struct and getNode function
// Define insert function
// Your code here

Hint

Use an array of 26 pointers for children to represent each letter a-z. Initialize all children to NULL and isEndOfWord to 0 in getNode(). In insert(), loop over each character, calculate index by subtracting 'a', create new nodes if needed, and mark the last node's isEndOfWord as 1.

2

Create Words Array and Root Trie Node

Create a char* array called words with these exact words: "apple", "app", "application", "bat", "ball". Then create a TrieNode* variable called root and set it to the result of getNode().

DSA C

#include 
#include 
#include 

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

TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = 0;
    for (int i = 0; i children[i] = NULL;
    }
    return node;
}

void insert(TrieNode* root, char* word) {
    TrieNode* current = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (current->children[index] == NULL) {
            current->children[index] = getNode();
        }
        current = current->children[index];
    }
    current->isEndOfWord = 1;
}

// Create words array and root node
// Your code here

Hint

Define the array words with the exact words given. Then create root as a pointer to TrieNode and assign it the result of getNode().

3

Insert Words into Trie and Implement Autocomplete Search

Use a for loop with variable i to insert each word from words into the Trie using insert(root, words[i]). Then implement a function TrieNode* searchNode(TrieNode* root, char* prefix) that returns the TrieNode where the prefix ends or NULL if prefix not found. Also implement a recursive function void suggestionsRec(TrieNode* root, char* prefix, char* buffer, int depth) that prints all words starting from the given node by appending characters to buffer. Finally, implement void printSuggestions(TrieNode* root, char* prefix) that uses searchNode and suggestionsRec to print all autocomplete suggestions for the prefix.

DSA C

#include 
#include 
#include 

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

TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = 0;
    for (int i = 0; i children[i] = NULL;
    }
    return node;
}

void insert(TrieNode* root, char* word) {
    TrieNode* current = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (current->children[index] == NULL) {
            current->children[index] = getNode();
        }
        current = current->children[index];
    }
    current->isEndOfWord = 1;
}

char* words[] = {"apple", "app", "application", "bat", "ball"};
TrieNode* root = NULL;
root = getNode();

// Insert words into Trie
for (int i = 0; i < 5; i++) {
    insert(root, words[i]);
}

// Implement searchNode function
// Implement suggestionsRec function
// Implement printSuggestions function
// Your code here

Hint

Insert all words using a loop. searchNode walks down the Trie for the prefix. suggestionsRec recursively prints all words from a node by adding letters to a buffer. printSuggestions calls these to print all autocomplete words or a message if none found.

4

Print Autocomplete Suggestions for a Prefix

Call printSuggestions(root, "app") to print all autocomplete suggestions for the prefix "app".

DSA C

#include 
#include 
#include 

// All previous code here

// Print suggestions for prefix "app"
printSuggestions(root, "app");

Hint

Call printSuggestions(root, "app") inside main() to print all words starting with "app".

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To store words in a tree structure for fast prefix search

B. To sort words alphabetically before searching

C. To store words in a linked list for sequential access

D. To compress words into a hash table for quick lookup

Solution

1. Step 1: Understand the role of Trie in autocomplete

   A Trie stores words character by character in a tree, allowing quick prefix matching.

2. Step 2: Compare with other data structures

   Linked lists and hash tables do not efficiently support prefix searches like Tries do.

3. Final Answer:

   To store words in a tree structure for fast prefix search -> Option A

4. Quick Check:

   Trie = fast prefix search [OK]

Hint: Trie = tree for prefixes, perfect for autocomplete [OK]

Common Mistakes:

• Confusing Trie with hash table
• Thinking linked list is efficient for prefix search
• Assuming sorting alone solves autocomplete

2. Which of the following is the correct way to declare a Trie node structure in C for lowercase English letters?

easy

A. typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode;

B. typedef struct TrieNode { struct TrieNode* children[52]; int isEndOfWord; } TrieNode;

C. typedef struct TrieNode { struct TrieNode* children[10]; int isEndOfWord; } TrieNode;

D. typedef struct TrieNode { struct TrieNode* children; int isEndOfWord; } TrieNode;

Solution

1. Step 1: Identify the size of children array for lowercase letters

   There are 26 lowercase English letters, so children array size should be 26.

2. Step 2: Check the structure correctness

   Each node has an array of pointers to children and a flag for end of word.

3. Final Answer:

   typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode; -> Option A

4. Quick Check:

   26 children for lowercase letters [OK]

Hint: 26 children pointers for lowercase English letters [OK]

Common Mistakes:

• Using 52 for uppercase + lowercase without clarification
• Using 10 for digits only
• Not using array for children pointers

3. Given the following code snippet inserting words into a Trie and searching for prefix "app":

insert("apple");
insert("app");
insert("application");
searchPrefix("app");

What will searchPrefix("app") return?

medium

A. ["app"]

B. ["app", "apple", "application"]

C. ["apple", "application"]

D. []

Solution

1. Step 1: Understand insertion of words

   Words "apple", "app", and "application" are inserted, all sharing prefix "app".

2. Step 2: Search prefix "app" returns all words starting with "app"

   So, it returns all three words: "app", "apple", and "application".

3. Final Answer:

   ["app", "apple", "application"] -> Option B

4. Quick Check:

   Prefix "app" matches 3 words [OK]

Hint: Prefix search returns all words starting with prefix [OK]

Common Mistakes:

• Returning only exact matches
• Missing shorter word "app"
• Returning empty list incorrectly

4. Consider this buggy C code snippet for inserting a word into a Trie:

void insert(TrieNode* root, const char* word) {
  TrieNode* node = root;
  for (int i = 0; word[i] != '\0'; i++) {
    int index = word[i] - 'a';
    if (node->children[index] == NULL) {
      node->children[index] = malloc(sizeof(TrieNode));
      memset(node->children[index], 0, sizeof(TrieNode));
    }
    node = node->children[index];
  }
  node->isEndOfWord = 1;
}

What is the main bug in this code?

medium

A. Root node is not checked for NULL

B. Index calculation is incorrect

C. isEndOfWord is set before loop

D. New nodes are not initialized after malloc

Solution

1. Step 1: Analyze malloc usage for new nodes

   malloc allocates memory but does not initialize children pointers or isEndOfWord flag.

2. Step 2: Consequence of missing initialization

   Uninitialized children pointers may cause undefined behavior during traversal or insertion.

3. Final Answer:

   New nodes are not initialized after malloc -> Option D

4. Quick Check:

   malloc needs initialization [OK]

Hint: Always initialize new Trie nodes after malloc [OK]

Common Mistakes:

• Assuming malloc zeroes memory
• Thinking index calculation is wrong
• Ignoring initialization of isEndOfWord

5. You want to extend a Trie-based autocomplete system to support case-insensitive search for English letters (both uppercase and lowercase). Which modification is the best approach?

hard

A. Store words as-is and compare characters ignoring case during search only

B. Increase children array size to 52 to store uppercase and lowercase separately

C. Convert all input words to lowercase before insertion and search, keep children array size 26

D. Use a hash map instead of array for children to store any character

Solution

1. Step 1: Consider memory and complexity

   Using 52 children doubles memory; hash map adds overhead; ignoring case only during search is inefficient.

2. Step 2: Normalize input for simplicity

   Converting all words to lowercase before insertion and search simplifies Trie structure and ensures consistent matching.

3. Final Answer:

   Convert all input words to lowercase before insertion and search, keep children array size 26 -> Option C

4. Quick Check:

   Normalize case before Trie operations [OK]

Hint: Normalize case before insert/search for simpler Trie [OK]

Common Mistakes:

• Doubling children array size unnecessarily
• Ignoring case only during search causes mismatch
• Using hash map adds complexity and overhead