Word Search in 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* createNode() {
    struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    node->isEndOfWord = [1];
    for (int i = 0; i < 26; i++) {
        node->children[i] = NULL;
    }
    return node;
}

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

A1

B0

CNULL

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting isEndOfWord to 1 by mistake.

Using NULL instead of 0 for a boolean flag.

The isEndOfWord flag should be initialized to 0 (false) when creating a new Trie node.

2fill in blank

medium

Complete the code to insert a word into the Trie.

DSA C

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

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

Ai

B0

Cword[i]

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using i instead of index to access children.

Using word[i] directly as an index.

We use the calculated index to access the children array for the current character.

3fill in blank

hard

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

DSA C

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

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

Aindex

Bi

Cword[i]

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using i instead of index to access children.

Using word[i] directly as an index.

We must use the index variable to move to the next child node corresponding to the current character.

4fill in blank

hard

Fill both blanks to implement a function that checks if any word in the Trie starts with a given prefix.

DSA C

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

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

Aindex

Bi

Cprefix[i]

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using i instead of index in one or both blanks.

Using prefix[i] directly as an index.

Both blanks should use the index variable to correctly traverse the Trie nodes for the prefix characters.

5fill in blank

hard

Fill all three blanks to implement a function that deletes the Trie and frees memory.

DSA C

void freeTrie(struct TrieNode* root) {
    if (root == NULL) return;
    for (int i = 0; i < [1]; i++) {
        if (root->children[[2]] != NULL) {
            freeTrie(root->children[[3]]);
        }
    }
    free(root);
}

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

A26

Bi

C0

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or root instead of the loop variable to access children.

Not looping through all 26 children.

We loop through all 26 children using index i, and recursively free each child node before freeing the root.

Practice

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

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To store words in a hash table

D. To perform arithmetic operations on words

Solution

1. Step 1: Understand Trie structure

   A Trie stores characters of words in a tree-like structure where each node represents a character.

2. Step 2: Identify Trie usage

   It allows quick prefix-based search by traversing nodes matching characters in order.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is for prefix-based word search, not sorting [OK]

Common Mistakes:

• Confusing Trie with hash tables
• Thinking Trie sorts words
• Assuming Trie stores whole words in one node

2. Which of the following is the correct way to check if a word exists in a Trie in C?

easy

A. Use a hash function on the word and check hash table

B. Check only the root node for the word

C. Sort the Trie nodes and do binary search

D. Traverse nodes for each character; if path ends early, word not found

Solution

1. Step 1: Understand Trie search logic

   Search each character by moving through child nodes; if any character node missing, word not found.

2. Step 2: Eliminate incorrect options

   Hash and sorting are unrelated to Trie search; root node alone can't hold whole word.

3. Final Answer:

   Traverse nodes for each character; if path ends early, word not found -> Option D

4. Quick Check:

   Trie search = character traversal [OK]

Hint: Check each character node in order to find word [OK]

Common Mistakes:

• Using hash or sorting instead of Trie traversal
• Checking only root node
• Assuming word is stored in one node

3. What will be the output of the following C code snippet that searches for the word "cat" in a Trie containing words "cat", "car", "dog"?

bool search(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]) return false;
        node = node->children[index];
    }
    return node->isEndOfWord;
}

// Assume Trie is built with words "cat", "car", "dog"
printf("%d", search(root, "cat"));

medium

A. 1

B. 0

C. Compilation error

D. Runtime error

Solution

1. Step 1: Analyze search function logic

   Function traverses Trie nodes for each character; returns true if last node marks end of word.

2. Step 2: Check if "cat" is in Trie

   "cat" was inserted, so traversal succeeds and isEndOfWord is true, returning 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Word found = 1 [OK]

Hint: If word inserted, search returns 1 (true) [OK]

Common Mistakes:

• Assuming search returns 0 for found words
• Confusing isEndOfWord flag
• Ignoring null checks in traversal

4. Identify the bug in this Trie search function in C:

bool search(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) return false;
        node = node->children[index];
    }
    return true;
}

medium

A. It uses wrong index calculation for characters

B. It does not check for NULL root pointer

C. It returns true without checking if node marks end of word

D. It should return false at the end instead of true

Solution

1. Step 1: Review return condition after loop

   Function returns true after traversal without verifying if current node marks end of a valid word.

2. Step 2: Understand Trie word end marking

   Words end at nodes with isEndOfWord true; missing this check causes false positives.

3. Final Answer:

   It returns true without checking if node marks end of word -> Option C

4. Quick Check:

   Must check isEndOfWord before returning true [OK]

Hint: Always check isEndOfWord after traversal [OK]

Common Mistakes:

• Skipping isEndOfWord check
• Not handling NULL root
• Incorrect index calculation

5. Given a Trie containing the words: "apple", "app", "ape", "bat", "bath", which of the following words will the search function return true for? Assume the search function correctly checks isEndOfWord.

hard

A. "ap" only

B. "bat", "bath", and "apple" only

C. "bat", "bathroom", and "apple" only

D. "bat" and "apple" only

Solution

1. Step 1: Identify words inserted in Trie

   Words inserted are "apple", "app", "ape", "bat", "bath"; only these have isEndOfWord true at last character.

2. Step 2: Check each option word

   "ap" is prefix but not a word; "bat", "bath", "apple" are present; "bathroom" not inserted.

3. Final Answer:

   "bat", "bath", and "apple" only -> Option B

4. Quick Check:

   Search true only for inserted words [OK]

Hint: Search true only for complete inserted words [OK]

Common Mistakes:

• Assuming prefixes are valid words
• Including words not inserted
• Ignoring isEndOfWord flag