Trie Search Operation in DSA C

Mental Model

A trie stores words by branching letters step-by-step. Searching means following branches for each letter to see if the word exists.

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 or get lost.

root
 ↓
 [c] -> [a] -> [t*]
        ↓
       [r] -> [s*]

* means end of a word

Dry Run Walkthrough

Input: Trie with words: cat, car, cars; search for 'cars'

Goal: Check if the word 'cars' exists in the trie

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

root -> [c] -> [a] -> [t*]
               ↓
              [r] -> [s*]

Why: We must find the first letter 'c' to start matching the word

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

root -> [c] -> [a] -> [t*]
               ↓
              [r] -> [s*]

Why: Next letter 'a' must be found to continue the search

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

root -> [c] -> [a] -> [t*]
               ↓
              [r] -> [s*]

Why: Next letter 'r' must be found to continue the search

Step 4: Move to node 'r', look for child 's'

root -> [c] -> [a] -> [t*]
               ↓
              [r] -> [s*]

Why: Next letter 's' must be found to continue the search

Step 5: Move to node 's', check if it marks end of word

root -> [c] -> [a] -> [r] -> [s*]

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

Result:

root -> [c] -> [a] -> [r] -> [s*]
Word 'cars' found

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.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() {
    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] == NULL) {
            curr->children[index] = getNode();
        }
        curr = curr->children[index];
    }
    curr->isEndOfWord = true;
}

// Search for 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] == NULL) {
            return false; // letter not found, word doesn't exist
        }
        curr = curr->children[index];
    }
    return curr != NULL && curr->isEndOfWord; // check end of word
}

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

    const char* word = "cars";
    if (search(root, word)) {
        printf("Word '%s' found\n", word);
    } else {
        printf("Word '%s' not found\n", word);
    }
    return 0;
}

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

iterate over each letter in the search word

int index = word[i] - 'a';

convert letter to index 0-25 for children array

if (curr->children[index] == NULL) { return false; }

if letter branch missing, word not found

curr = curr->children[index];

move to next node matching current letter

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

check if current node marks end of a valid word

Output

Word 'cars' found

Complexity Analysis

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

Space: O(1) because search uses only a few pointers, no extra space grows with input

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

Edge Cases

search for empty string

returns false because no word is empty in trie

DSA C

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

search for word not in trie

returns false when a letter branch is missing

DSA C

if (curr->children[index] == NULL) { return false; }

search for prefix but not full word

returns false if node exists but 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 trie search because it follows letter branches efficiently.

Common Mistakes

Mistake: Not checking if the final node marks end of a word, causing false positives for prefixes
Fix: Always check isEndOfWord flag after traversing all letters

Summary

It checks if a word exists by following letter nodes step-by-step in the trie.

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

The key is to follow each letter branch and confirm the last node marks a complete word.

Practice

1. What does the search operation in a Trie data structure primarily check for?

easy

A. The number of words stored in the Trie

B. If the Trie is empty

C. If a given word exists in the Trie

D. The length of the longest word in the Trie

Solution

1. Step 1: Understand the purpose of Trie search

   The search operation in a Trie is designed to check if a specific word is present by traversing nodes corresponding to each character.

2. Step 2: Identify what the search confirms

   If all characters of the word are found sequentially and the last node marks the end of a word, the word exists in the Trie.

3. Final Answer:

   If a given word exists in the Trie -> Option C

4. Quick Check:

   Trie search checks word existence = C [OK]

Hint: Search checks presence of full word in Trie [OK]

Common Mistakes:

• Confusing search with counting words
• Thinking search checks Trie emptiness
• Assuming search returns word length

2. Which of the following is the correct way to check if a character node exists in a Trie during search in C?

easy

A. if (node->children[c] == NULL)

B. if (node->children[c - 'a'] != NULL)

C. if (node->children[c + 'a'] != NULL)

D. if (node->children[c] != 0)

Solution

1. Step 1: Understand character indexing in Trie

   Characters are mapped to array indices by subtracting 'a' to get 0-based index for children array.

2. Step 2: Check for non-null child node

   To verify if a child node exists for character c, check if node->children[c - 'a'] is not NULL.

3. Final Answer:

   if (node->children[c - 'a'] != NULL) -> Option B

4. Quick Check:

   Index = c - 'a', check != NULL = B [OK]

Hint: Use c - 'a' to index children array in Trie [OK]

Common Mistakes:

• Using c directly as index without subtracting 'a'
• Checking for NULL with wrong comparison
• Adding 'a' to c instead of subtracting

3. Given the following Trie search code snippet in C, what will be the output if we search for "cat" after inserting "car" and "cat"?

bool search(struct TrieNode* root, const char* word) {
    struct 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 node->isEndOfWord;
}

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Understand inserted words and search target

   Words "car" and "cat" are inserted, so nodes for 'c', 'a', 'r' and 't' exist with isEndOfWord true at 'r' and 't'.

2. Step 2: Trace search for "cat"

   Search traverses 'c' -> 'a' -> 't' nodes, all present, and node->isEndOfWord is true at 't', so returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Inserted "cat" found = true [OK]

Hint: Search returns true if word was inserted before [OK]

Common Mistakes:

• Assuming search returns false if similar word exists
• Confusing isEndOfWord with node presence
• Ignoring null checks in loop

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

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

medium

A. Infinite loop due to missing increment

B. Does not check for NULL root

C. Incorrect indexing of children array

D. Returns false even if word exists

Solution

1. Step 1: Analyze return statement after loop

   The function returns false after loop ends, ignoring if current node marks end of word.

2. Step 2: Identify missing check for word completion

   It should return node->isEndOfWord to confirm full word presence, but returns false always.

3. Final Answer:

   Returns false even if word exists -> Option D

4. Quick Check:

   Missing isEndOfWord check causes false return [OK]

Hint: Return node->isEndOfWord after loop to confirm word [OK]

Common Mistakes:

• Forgetting to check isEndOfWord at end
• Assuming node presence means word exists
• Ignoring root NULL check (less critical here)

5. You have a Trie storing words: "bat", "bath", "baton", "bar", and "barn". Which of the following search queries will return false? "bathe", "bar", "bat", "barn"

hard

A. "bathe"

B. "bar"

C. "bat"

D. "barn"

Solution

1. Step 1: Check each query word against inserted words

   "bathe" is not inserted; "bar", "bat", and "barn" are inserted words in the Trie.

2. Step 2: Understand Trie search returns false for non-inserted words

   Since "bathe" is not inserted, search will fail at 'h' or after, returning false.

3. Final Answer:

   "bathe" -> Option A

4. Quick Check:

   Non-inserted word returns false = "bathe" [OK]

Hint: Search false if word not fully inserted in Trie [OK]

Common Mistakes:

• Assuming prefix words always return true
• Confusing prefix presence with full word presence
• Ignoring isEndOfWord flag in search