Word Search in Trie 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 each node represents a character of a word. It allows fast retrieval of words by their prefixes.

beginner

How does searching a word in a Trie work?

Start from the root and follow the nodes matching each character of the word. If all characters are found and the last node marks the end of a word, the word exists in the Trie.

beginner

What does the 'end of word' marker in a Trie node signify?

It indicates that the path from the root to this node forms a complete valid word stored in the Trie.

intermediate

Why is Trie efficient for prefix-based searches?

Because common prefixes share the same path in the Trie, searching for words with the same prefix is faster and avoids repeated comparisons.

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, since each character is checked once along the path.

What does each node in a Trie represent?

A A whole word

B A sentence

C A number

D A character of a word

Each node in a Trie represents a single character of a word.

How do you know a word ends in a Trie?

A When the node is marked as end of word

B When the node has no children

C When the node has exactly one child

D When the node is the root

A node marked as end of word indicates the complete word ends there.

What is the main advantage of using a Trie for word search?

A Sorts words automatically

B Faster search by prefix

C Stores numbers efficiently

D Uses less memory than arrays

Trie allows fast search for words sharing common prefixes.

What is the worst-case time complexity to search a word of length m in a Trie?

A O(m)

B O(1)

C O(log m)

D O(m^2)

Searching a word requires checking each character once, so O(m).

If a word is not found in a Trie, what happens during search?

A Search loops infinitely

B Search completes successfully

C Search reaches a null or missing node before word ends

D Search returns the closest word

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

Explain how to search for a word in a Trie step-by-step.

Think about moving through nodes for each letter.

Describe why Tries are useful for prefix-based word searches.

Imagine words like 'cat' and 'car' sharing the same start.

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