Autocomplete System with Trie in DSA C

Mental Model

A trie stores words by sharing common prefixes so we can quickly find all words starting with a given prefix.

Analogy: Imagine a tree of roads where each road sign is a letter. To find all places starting with 'ca', you follow the roads for 'c' then 'a' and see all branches from there.

root
 |
 c
 |
 a
 |
 t (end)
 |
 r
 |
 e (end)

Each node points to next letters forming words like 'cat' and 'care'.

Dry Run Walkthrough

Input: Insert words: 'cat', 'car', 'care'; autocomplete prefix: 'ca'

Goal: Find all words starting with 'ca' using the trie

Step 1: Insert 'cat' letter by letter into trie

root -> c -> a -> t[end]

Only 'cat' inserted so far

Why: We build the path for 'cat' so it can be found later

Step 2: Insert 'car' sharing prefix 'ca', add 'r' node

root -> c -> a -> t[end]
               -> r[end]

'car' shares 'ca' with 'cat'

Why: Sharing prefix saves space and speeds search

Step 3: Insert 'care' extending from 'car' with 'e' node

root -> c -> a -> t[end]
               -> r -> e[end]

'care' extends 'car'

Why: Trie grows only new letters beyond shared prefix

Step 4: Search prefix 'ca' by following nodes c -> a

At node 'a' with children t[end], r -> e[end]

Why: We reach the prefix node to find all words starting with 'ca'

Step 5: Collect all words from 'a' node: 'cat', 'car', 'care'

Words found: 'cat', 'car', 'care'

Why: All words under prefix node are autocomplete suggestions

Result:

root -> c -> a -> t[end]
               -> r -> e[end]
Autocomplete results for 'ca': cat, car, care

Annotated Code

DSA C

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

#define ALPHABET_SIZE 26

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

// Create a new trie node
TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++)
        node->children[i] = NULL;
    return node;
}

// Insert a word into the trie
void insert(TrieNode* root, const char* word) {
    TrieNode* curr = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (curr->children[index] == NULL) {
            curr->children[index] = getNode();
        }
        curr = curr->children[index]; // advance curr to next letter node
    }
    curr->isEndOfWord = true; // mark end of word
}

// Recursive helper to collect all words from given node
void collectWords(TrieNode* node, char* prefix, int length) {
    if (node->isEndOfWord) {
        prefix[length] = '\0';
        printf("%s\n", prefix); // print found word
    }
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->children[i] != NULL) {
            prefix[length] = 'a' + i;
            collectWords(node->children[i], prefix, length + 1); // explore deeper
        }
    }
}

// Autocomplete function: find all words with given prefix
void autocomplete(TrieNode* root, const char* prefix) {
    TrieNode* curr = root;
    int length = strlen(prefix);
    for (int i = 0; i < length; i++) {
        int index = prefix[i] - 'a';
        if (curr->children[index] == NULL) {
            printf("No words found with prefix '%s'\n", prefix);
            return; // prefix not found
        }
        curr = curr->children[index]; // move to prefix node
    }
    char buffer[100];
    strcpy(buffer, prefix);
    collectWords(curr, buffer, length); // collect all words under prefix
}

int main() {
    TrieNode* root = getNode();
    insert(root, "cat");
    insert(root, "car");
    insert(root, "care");

    printf("Autocomplete results for 'ca':\n");
    autocomplete(root, "ca");

    return 0;
}

curr = curr->children[index]; // advance curr to next letter node

advance curr to next node to build or traverse the word path

curr->isEndOfWord = true; // mark end of word

mark current node as end of a valid word

if (curr->children[index] == NULL) { curr->children[index] = getNode(); }

create new node if path letter does not exist

if (node->isEndOfWord) { prefix[length] = '\0'; printf("%s\n", prefix); }

print word when end of word node reached

autocomplete: if (curr->children[index] == NULL) { printf("No words found..."); return; }

stop if prefix path does not exist

collectWords(curr, buffer, length); // collect all words under prefix

start recursive collection of words from prefix node

Output

Autocomplete results for 'ca':

cat

car

care

Complexity Analysis

Time: O(m + n) where m is length of prefix and n is total letters in all matching words because we traverse prefix then collect all words under it

Space: O(n) for trie nodes storing all inserted words and recursion stack during collection

vs Alternative: Compared to scanning all words linearly (O(total words * average length)), trie reduces search to prefix length plus relevant subtree traversal, making autocomplete faster

Edge Cases

Empty trie (no words inserted)

Autocomplete returns no words found

DSA C

if (curr->children[index] == NULL) { printf("No words found with prefix '%s'\n", prefix); return; }

Prefix not present in trie

Autocomplete returns no words found

DSA C

if (curr->children[index] == NULL) { printf("No words found with prefix '%s'\n", prefix); return; }

Prefix is a complete word and also prefix of other words

Autocomplete returns the prefix word and all longer words

DSA C

if (node->isEndOfWord) { prefix[length] = '\0'; printf("%s\n", prefix); }

When to Use This Pattern

When you need to quickly find all words starting with a prefix, use a trie-based autocomplete because it shares prefixes and speeds up search.

Common Mistakes

Mistake: Not marking the end of word node, so autocomplete returns incomplete results
Fix: Set isEndOfWord = true at the last node of each inserted word

Mistake: Not checking if child node exists before accessing, causing crashes
Fix: Always check if curr->children[index] is NULL before moving or creating new node

Summary

Stores words in a tree sharing prefixes to quickly find all words starting with a prefix.

Use when you want fast autocomplete suggestions from a large dictionary.

The key is to follow prefix nodes then collect all words below that node.

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