Word Search in Trie in DSA C - Execution Trace

Concept Flow - Word Search in Trie

Start at root node

↓

Check first char in word

↓

Char found in children?

No→Word NOT found

Yes↓

Move to child node

↓

More chars left?

No→Check isEnd flag

↓

Word found if isEnd==true

↓

Repeat for next char

↓

Done

Start from root, check each character in the word by moving through child nodes. If any char missing, word not found. If all chars found, check end flag.

Execution Sample

DSA C

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

Searches a word in the trie by traversing nodes for each character and returns true if word exists.

Execution Table

Step	Operation	Current Char	Node Visited	Pointer Changes	Visual State
1	Start at root	-	root	current = root	root -> [a,b,c,...]
2	Check char 'c'	c	root	current = root->children['c']	root -> c -> [...]
3	Char 'c' found	c	node 'c'	move current to 'c'	root -> c -> a -> [...]
4	Check char 'a'	a	node 'c'	current = c->children['a']	root -> c -> a -> [...]
5	Char 'a' found	a	node 'a'	move current to 'a'	root -> c -> a -> t -> [...]
6	Check char 't'	t	node 'a'	current = a->children['t']	root -> c -> a -> t (isEnd=true)
7	Char 't' found	t	node 't'	move current to 't'	root -> c -> a -> t (isEnd=true)
8	No more chars	-	node 't'	-	Check isEnd flag = true
9	Word found	-	node 't'	-	Return true
10	End	-	-	-	Search complete

💡 Search ends when all characters are found and isEnd flag is true, else false if any char missing.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
current	root	node 'c'	node 'a'	node 't'	node 't'
current char	-	'c'	'a'	't'	-
isEnd flag	-	-	-	true	true

Key Moments - 3 Insights

Why do we check the isEnd flag after traversing all characters?

Because the path may exist for a prefix but not a complete word. The isEnd flag confirms the node marks the end of a valid word (see execution_table step 8).

What happens if a character is not found in children nodes?

The search returns false immediately, meaning the word does not exist in the trie (see execution_table step 3 if char missing).

Why do we move the current pointer to the child node for each character?

To traverse down the trie along the path representing the word. Each move narrows down the search to the next character node (see execution_table steps 3,5,7).

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'current' node after checking character 'a'?

A node 'c'

B node 'a'

C node 't'

D root

💡 Hint

Refer to execution_table row 4 and variable_tracker column 'After Step 4' for 'current' variable.

At which step does the search confirm the word exists by checking the isEnd flag?

A Step 8

B Step 6

C Step 3

D Step 10

💡 Hint

Look at execution_table step 8 where isEnd flag is checked after all chars are processed.

If the character 'a' was missing from node 'c', what would happen in the execution_table?

A Search would continue to next character

B Return true immediately

C Return false immediately

D Check isEnd flag at node 'c'

💡 Hint

Refer to key_moments about missing character causing immediate false return.

Concept Snapshot

Word Search in Trie:
- Start at root node
- For each char in word, move to child node
- If child missing, word not found
- After last char, check isEnd flag
- Return true if isEnd is true, else false

Full Transcript

This visualization shows how to search a word in a trie data structure. We start at the root node and check each character of the word one by one. For each character, we look for a child node matching that character. If the child node exists, we move the current pointer to that node and continue. If any character is missing, the search ends returning false, meaning the word is not in the trie. After all characters are found, we check the isEnd flag on the last node to confirm if it marks the end of a valid word. If true, the word exists; otherwise, it does not. The execution table tracks each step, showing the current node and pointer changes. The variable tracker shows how the current pointer and characters change during the search. Key moments clarify why the isEnd flag is important and what happens if a character is missing. The quiz tests understanding of these steps.

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