Trie Search Operation in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths down the tree represent words.

beginner

How does the search operation work in a Trie?

Search starts from the root and follows the path of characters in the word. If all characters are found in sequence and the last node marks the end of a word, the search is successful.

beginner

What does it mean if a search in a Trie fails at some character?

It means the word is not present in the Trie because the path for that character does not exist from the current node.

intermediate

Why is Trie search efficient for prefix-based queries?

Because Trie nodes represent prefixes, searching for words with a common prefix shares the same path, making prefix queries fast and memory efficient.

intermediate

What is the time complexity of searching a word in a Trie?

The time complexity is O(m), where m is the length of the word being searched, because each character is checked once along the path.

In a Trie search, what does reaching a node that marks the end of a word indicate?

A The word exists in the Trie

B The word does not exist

C The Trie is empty

D The search should restart

If the last character node of the search path marks the end of a word, it means the word exists in the Trie.

What happens if a character in the search word is not found in the current Trie node's children?

A The search restarts from root

B The search continues with next character

C The Trie inserts the character automatically

D The search fails; word not found

If a character is missing in the children nodes, the word does not exist in the Trie.

What is the starting point for a Trie search operation?

A Random node

B Leaf node

C Root node

D Middle node

Trie search always starts from the root node.

Which of these best describes the Trie search time complexity?

A O(n), where n is number of words

B O(m), where m is word length

C O(log n)

D O(1)

Search time depends on the length of the word, not the number of words stored.

Why is Trie search useful for autocomplete features?

A Because it quickly finds all words sharing a prefix

B Because it sorts words alphabetically

C Because it stores words in a list

D Because it uses hashing

Trie structure allows fast retrieval of all words with a given prefix, ideal for autocomplete.

Explain step-by-step how a search operation works in a Trie for the word "cat".

Think about following each character one by one from root.

What are the possible reasons a search for a word in a Trie might fail?

Consider missing nodes or incomplete word marking.

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