Prefix Search Using Trie in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new Trie node.

DSA C

struct TrieNode* getNode() {
    struct TrieNode* pNode = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    pNode->isEndOfWord = [1];
    for (int i = 0; i < 26; i++)
        pNode->children[i] = NULL;
    return pNode;
}

Drag options to blanks, or click blank then click option'

A1

BNULL

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting isEndOfWord to 1 initially, which incorrectly marks the node as end of a word.

When creating a new Trie node, isEndOfWord should be initialized to 0 (false) because no word ends at this node yet.

2fill in blank

medium

Complete the code to insert a word into the Trie.

DSA C

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

Drag options to blanks, or click blank then click option'

ApCrawl

Bindex

Ckey[level]

Dlevel

Attempts:

3 left

💡 Hint

Common Mistakes

Using the loop variable 'level' directly as index.

Using the character instead of index to access children.

We check if the child at position 'index' is NULL before creating a new node.

3fill in blank

hard

Fix the error in the search function to correctly check if a prefix exists in the Trie.

DSA C

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

Drag options to blanks, or click blank then click option'

A1

BpCrawl->isEndOfWord

C0

DpCrawl == NULL

Attempts:

3 left

💡 Hint

Common Mistakes

Returning pCrawl->isEndOfWord which only checks full words, not prefixes.

For prefix search, we return 1 if all characters are found, regardless of isEndOfWord.

4fill in blank

hard

Fill both blanks to implement a function that counts how many words start with a given prefix.

DSA C

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

int countWords(struct TrieNode* node) {
    int count = 0;
    if (node->isEndOfWord)
        count++;
    for (int i = 0; i < 26; i++) {
        if (node->children[i])
            count += [2](node->children[i]);
    }
    return count;
}

Drag options to blanks, or click blank then click option'

AcountWords

Bsearch

Cinsert

DgetNode

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert or search functions instead of counting recursively.

The function recursively counts words starting from the prefix node using countWords.

5fill in blank

hard

Fill all three blanks to implement a function that deletes a word from the Trie and cleans up unused nodes.

DSA C

int deleteWord(struct TrieNode* node, const char* key, int depth) {
    if (!node)
        return 0;
    if (key[depth] == '\0') {
        if (node->isEndOfWord)
            node->isEndOfWord = 0;
        if ([1](node)) {
            free(node);
            return 1;
        }
        return 0;
    }
    int index = key[depth] - 'a';
    if (deleteWord(node->children[[2]], key, depth + 1)) {
        node->children[index] = NULL;
        if (!node->isEndOfWord && [3](node)) {
            free(node);
            return 1;
        }
    }
    return 0;
}

int isEmpty(struct TrieNode* node) {
    for (int i = 0; i < 26; i++)
        if (node->children[i])
            return 0;
    return 1;
}

Drag options to blanks, or click blank then click option'

AisEmpty

Bindex

Cdepth

DdeleteWord

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variable for child access.

Not checking if node is empty before freeing.

We use isEmpty to check if node has no children, index to access child, and isEmpty again to check if parent can be freed.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To perform arithmetic operations quickly

B. To sort words alphabetically

C. To store numbers in sorted order

D. To efficiently find all words that start with a given prefix

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie stores characters of words in a tree structure, allowing quick prefix lookups.

2. Step 2: Identify the main use case

   It helps find all words starting with a prefix efficiently, unlike sorting or arithmetic.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option D

4. Quick Check:

   Trie = Prefix search efficiency [OK]

Hint: Trie is built for prefix-based word retrieval [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie is for arithmetic
• Assuming Trie stores numbers only

2. Which of the following is the correct way to declare a Trie node structure in C for prefix search?

easy

A. typedef struct TrieNode { int data; struct TrieNode* next; } TrieNode;

B. typedef struct TrieNode { char* word; struct TrieNode* child; } TrieNode;

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

D. typedef struct TrieNode { int value; struct TrieNode* left; struct TrieNode* right; } TrieNode;

Solution

1. Step 1: Identify Trie node components

   A Trie node has an array of pointers for each alphabet letter and a flag for word end.

2. Step 2: Match with given options

   typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode; matches this structure with 26 children pointers and an end-of-word flag.

3. Final Answer:

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

4. Quick Check:

   Trie node = children array + end flag [OK]

Hint: Trie nodes have 26 children pointers for letters a-z [OK]

Common Mistakes:

• Using linked list pointers instead of array for children
• Confusing Trie node with linked list or binary tree node
• Missing end-of-word flag

3. Given the following code snippet inserting words "cat", "car", and "dog" into a Trie, what will be the output of searching prefix "ca"?

insert("cat");
insert("car");
insert("dog");
searchPrefix("ca");

medium

A. ["cat", "car"]

B. ["dog"]

C. ["cat"]

D. []

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted, building branches for 'c' and 'd'.

2. Step 2: Search prefix "ca"

   Both "cat" and "car" start with "ca", so they are returned by searchPrefix.

3. Final Answer:

   ["cat", "car"] -> Option A

4. Quick Check:

   Prefix "ca" matches cat and car [OK]

Hint: Words starting with prefix are returned [OK]

Common Mistakes:

• Returning only one matching word
• Returning words not matching prefix
• Empty result for existing prefix

4. Consider this buggy C code snippet for inserting a word into a Trie. What is the main error?

void insert(TrieNode* root, 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));
    }
    node = node->children[index];
  }
  node->isEndOfWord = 1;
}

medium

A. New nodes are not initialized after malloc

B. Index calculation is incorrect

C. Loop condition should be i < strlen(word)

D. isEndOfWord flag is set too early

Solution

1. Step 1: Analyze node creation

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

2. Step 2: Identify impact

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

3. Final Answer:

   New nodes are not initialized after malloc -> Option A

4. Quick Check:

   malloc needs initialization [OK]

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

Common Mistakes:

• Assuming malloc zeroes memory
• Ignoring initialization of isEndOfWord
• Misunderstanding loop condition

5. You want to find all words in a Trie that start with prefix "app" and have length exactly 5. Which approach correctly combines prefix search and length filtering?

hard

A. Collect all words in Trie, then filter those starting with "app" and length 5

B. Traverse Trie to node for "app", then collect words of length 5 from there

C. Search for "app" as a full word, then check length 5

D. Use binary search on sorted word list for prefix "app" and length 5

Solution

1. Step 1: Use Trie prefix traversal

   Traverse the Trie to the node representing the prefix "app" to limit search space.

2. Step 2: Collect words of length 5 from that node

   From this node, recursively collect words that complete to length 5.

3. Final Answer:

   Traverse Trie to node for "app", then collect words of length 5 from there -> Option B

4. Quick Check:

   Prefix traversal + length filter = Traverse Trie to node for "app", then collect words of length 5 from there [OK]

Hint: Start at prefix node, then filter by length [OK]

Common Mistakes:

• Filtering all words instead of prefix subtree
• Searching prefix as full word
• Using binary search on Trie data