Word Search in Trie in DSA C

Mental Model

A trie stores words by sharing common prefixes, so searching a word means following the path of its letters in the trie.

Analogy: Imagine a tree of roads where each road sign is a letter. To find a word, you follow the signs letter by letter until you reach the end of the word.

root
 ↓
 [c] -> [a] -> [t] (end)
           ↓
          [r] -> [a] -> [t] (end)

Each bracket is a node holding a letter. Arrows show links to next letters.

Dry Run Walkthrough

Input: Trie with words: cat, car, rat; search word: car

Goal: Check if 'car' exists in the trie

Step 1: Start at root, look for child node 'c'

root -> [c] -> [a] -> [t] (end), [r] -> [a] -> [t] (end)

Why: We must find the first letter of the word to start the search

Step 2: Move to node 'c', look for child 'a'

[c] -> [a] -> [t] (end), [r] -> [a] -> [t] (end)

Why: Next letter 'a' must be found among children of 'c'

Step 3: Move to node 'a', look for child 'r'

[a] -> [t] (end), [r] -> [a] -> [t] (end)

Why: Next letter 'r' must be found among children of 'a'

Step 4: Move to node 'r', check if it marks end of word

[r] (end) -> [a] -> [t] (end)

Why: If this node marks end of word, 'car' exists in trie

Result:

root -> c -> a -> r (end)
Answer: 'car' found in trie

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.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(void) {
    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])
            curr->children[index] = getNode();
        curr = curr->children[index]; // advance curr to next letter node
    }
    curr->isEndOfWord = true; // mark end of word
}

// Search a word in the trie
bool search(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])
            return false; // letter path missing
        curr = curr->children[index]; // advance curr to next letter node
    }
    return curr != NULL && curr->isEndOfWord; // check end of word
}

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

    const char* word = "car";
    if (search(root, word))
        printf("%s found in trie\n", word);
    else
        printf("%s not found in trie\n", word);

    return 0;
}

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

advance curr pointer to child node matching current letter

if (!curr->children[index]) return false; // letter path missing

if next letter node missing, word not in trie

return curr != NULL && curr->isEndOfWord; // check end of word

confirm current node marks end of a stored word

Output

car found in trie

Complexity Analysis

Time: O(m) because we check each of the m letters of the word once

Space: O(n * m) where n is number of words and m average length, for trie storage

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster as it avoids full word comparisons

Edge Cases

searching empty string

returns false because no letters to follow

DSA C

for (int i = 0; word[i] != '\0'; i++) {

searching word not in trie

returns false when letter path missing

DSA C

if (!curr->children[index]) return false;

searching prefix of a word but not a full word

returns false because isEndOfWord is false

DSA C

return curr != NULL && curr->isEndOfWord;

When to Use This Pattern

When you need to quickly check if a word or prefix exists among many words, use a trie search because it follows letter paths efficiently.

Common Mistakes

Mistake: Not checking if the node marks the end of a word after traversing all letters
Fix: Always check isEndOfWord to confirm full word presence, not just prefix

Summary

It checks if a word exists by following its letters in the trie nodes.

Use it when you want fast word lookups among many stored words.

The key is that each letter leads to the next node, and the last node must mark the word's end.

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