Word Search in 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 C code that inserts words into a Trie and searches for a word?

DSA C

/* Trie node structure */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26

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

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

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

int search(TrieNode* root, const char* key) {
    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 (pCrawl != NULL && pCrawl->isEndOfWord);
}

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

A Compilation error

B 0

C 1

D Runtime error

💡 Hint

Check if the word 'app' was inserted and if the search function returns 1 for found words.

The word 'app' was inserted into the Trie, so searching for 'app' returns 1 indicating it is found.

🧠 Conceptual

intermediate

Trie Node Children Count

In a Trie node for lowercase English letters, how many children pointers does each node have?

A 26

B 52

C 10

D 128

💡 Hint

Consider the number of lowercase English letters.

Each Trie node has 26 children pointers, one for each lowercase English letter from 'a' to 'z'.

❓ Predict Output

advanced

Output of Trie Search for Non-Inserted Word

What is the output of this C code when searching for the word 'batman' after inserting 'bat' and 'ball'?

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26

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

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

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

int search(TrieNode* root, const char* key) {
    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 (pCrawl != NULL && pCrawl->isEndOfWord);
}

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

A 1

B 0

C Compilation error

D Segmentation fault

💡 Hint

Check if 'batman' was inserted or not.

The word 'batman' was not inserted, so the search returns 0 indicating not found.

🔧 Debug

advanced

Identify the Bug in Trie Search Function

What error will this Trie search function cause when searching for a word?

DSA C

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

// Assume root is NULL and search is called with root and "test"

A Segmentation fault due to dereferencing NULL root

B Returns 0 safely

C Compilation error due to missing return

D Infinite loop

💡 Hint

What happens if root is NULL and you try to access its children?

If root is NULL, accessing pCrawl->children causes a segmentation fault (crash) because you dereference a NULL pointer.

🚀 Application

expert

Number of Words Stored in Trie

Given a Trie where the following words are inserted: "cat", "car", "cart", "dog", "dot", what is the total number of words stored in the Trie?

A 6

B 4

C 3

D 5

💡 Hint

Count each inserted word as one stored word.

Each inserted word counts as one stored word regardless of shared prefixes.

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