Autocomplete System with Trie in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Insertion and Search

What is the output of the following code that inserts words into a Trie and searches for a prefix?

DSA C

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 < 26; i++)
        node->children[i] = NULL;
    return node;
}

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

int searchPrefix(TrieNode* root, const char* prefix) {
    TrieNode* pCrawl = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';
        if (!pCrawl->children[index])
            return 0;
        pCrawl = pCrawl->children[index];
    }
    return 1;
}

int main() {
    TrieNode* root = getNode();
    insert(root, "apple");
    insert(root, "app");
    insert(root, "bat");
    insert(root, "bath");
    printf("%d\n", searchPrefix(root, "app"));
    printf("%d\n", searchPrefix(root, "bat"));
    printf("%d\n", searchPrefix(root, "bath"));
    printf("%d\n", searchPrefix(root, "batman"));
    return 0;
}

A

1
0
1
0

B

1
1
0
0

C

0
1
1
0

D

1
1
1
0

💡 Hint

Check if the prefix exists in the Trie nodes after insertion.

The prefixes "app", "bat", and "bath" exist in the Trie, so searchPrefix returns 1 for them. "batman" does not exist as a prefix, so it returns 0.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which statement correctly describes the memory usage of a Trie node in this implementation?

A Each node contains a hash map of children and no end of word flag.

B Each node contains an array of 26 pointers and a flag indicating end of word.

C Each node contains a linked list of child nodes and a flag indicating end of word.

D Each node contains only a flag indicating if it is end of word.

💡 Hint

Look at the struct definition and what fields it contains.

The TrieNode struct has an array of 26 pointers for each letter and an integer flag isEndOfWord.

🔧 Debug

advanced

Identify the Bug in Trie Search Function

What error will occur when running this search function if the prefix contains uppercase letters?

DSA C

int searchPrefix(TrieNode* root, const char* prefix) {
    TrieNode* pCrawl = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';
        if (!pCrawl->children[index])
            return 0;
        pCrawl = pCrawl->children[index];
    }
    return 1;
}

A Accessing children with negative index causing undefined behavior.

B No error, function works correctly for uppercase letters.

C Compilation error due to invalid pointer usage.

D Memory leak due to missing free calls.

💡 Hint

Consider ASCII values of uppercase letters and how index is calculated.

Uppercase letters have ASCII codes less than 'a', so index becomes negative, causing invalid array access.

🚀 Application

advanced

Autocomplete Suggestions Using Trie

Given a Trie with words inserted, which approach correctly collects all words starting with a given prefix?

A Traverse to prefix node, then recursively collect all words from that node.

B Search each word in the Trie to check if it starts with prefix.

C Use a hash map to store all words and filter by prefix at runtime.

D Traverse the Trie from root and print all words regardless of prefix.

💡 Hint

Think about efficient traversal starting from the prefix node.

The efficient way is to find the node matching the prefix, then recursively collect all words below it.

❓ Predict Output

expert

Output of Trie Deletion Operation

What is the output after deleting the word "app" from the Trie containing "apple", "app", "application" and then searching for "app" and "apple"?

DSA C

int deleteWord(TrieNode* root, const char* key, int depth) {
    if (!root) return 0;
    if (key[depth] == '\0') {
        if (root->isEndOfWord) root->isEndOfWord = 0;
        for (int i = 0; i < 26; i++)
            if (root->children[i]) return 0;
        return 1;
    }
    int index = key[depth] - 'a';
    if (deleteWord(root->children[index], key, depth + 1)) {
        free(root->children[index]);
        root->children[index] = NULL;
        if (!root->isEndOfWord) {
            for (int i = 0; i < 26; i++)
                if (root->children[i]) return 0;
            return 1;
        }
        else return 0;
    }
    return 0;
}

int main() {
    TrieNode* root = getNode();
    insert(root, "apple");
    insert(root, "app");
    insert(root, "application");
    deleteWord(root, "app", 0);
    printf("%d\n", searchPrefix(root, "app"));
    printf("%d\n", searchPrefix(root, "apple"));
    return 0;
}

A

1
0

B

0
1

C

1
1

D

0
0

💡 Hint

Deleting "app" should not remove "apple" or "application" prefixes.

After deleting "app", the prefix "app" still exists because "apple" and "application" share it. So searchPrefix("app") returns 1 and searchPrefix("apple") returns 1.

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