Trie Search Operation in DSA C - Build from Scratch

Trie Search Operation

📖 Scenario: Imagine you are building a simple phone directory that can quickly check if a name exists in the list. You will use a Trie data structure to store names and then search for a specific name.

🎯 Goal: Build a Trie data structure to store a list of names and implement a search operation to check if a given name exists in the Trie.

📋 What You'll Learn

Create a Trie node structure with children and end-of-word marker

Insert given names into the Trie

Implement a search function to find if a name exists

Print the search result as 1 if found, 0 if not found

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete features, spell checkers, and IP routing to quickly find words or prefixes.

💼 Career

Understanding Trie operations is important for roles involving text processing, search engines, and efficient data retrieval.

1

Create Trie Node Structure and Insert Names

Define a struct called TrieNode with an array children of size 26 for letters 'a' to 'z' and an integer isEndOfWord. Then create a function getNode() that returns a new TrieNode with all children set to NULL and isEndOfWord set to 0. Finally, insert these exact names into the Trie using a function insert(): "apple", "app", "bat".

DSA C

// Define TrieNode struct and getNode function
// Insert "apple", "app", and "bat" into the Trie
// Your code here

Hint

Remember to create a struct with an array of 26 pointers for each letter and a flag for end of word. Then write a function to create and initialize a new node. Use the insert function to add each name letter by letter.

2

Add Search Function Configuration

Create a function called search() that takes the Trie root and a string key as input and returns 1 if the key exists in the Trie and 0 otherwise. Use a variable pCrawl to traverse the Trie nodes.

DSA C

#include 
#include 
#include 

#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 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;
}

// Create a function called search that returns 1 if key exists, else 0
// Your code here

int main() {
    TrieNode* root = getNode();
    insert(root, "apple");
    insert(root, "app");
    insert(root, "bat");
    return 0;
}

Hint

Use a loop to check each character of the key. If at any point the child node is NULL, return 0. After the loop, check if the current node marks the end of a word and return 1 if yes.

3

Search for a Specific Name in the Trie

Use the search() function to check if the name "app" exists in the Trie. Store the result in an integer variable called result.

DSA C

#include 
#include 
#include 

#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 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");

    // Search for "app" and store result
    int result;
    // Your code here

    return 0;
}

Hint

Call the search function with root and "app" as arguments. Store the returned value in an integer variable named result.

4

Print the Search Result

Print the value of the variable result using printf to display 1 if the name "app" exists in the Trie or 0 if it does not.

DSA C

#include 
#include 
#include 

#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 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");

    int result = search(root, "app");

    // Print the result
    printf("%d\n", result);

    return 0;
}

Hint

Use printf("%d\n", result); to print the integer result with a newline.

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