Trie Search Operation in DSA C - Execution Trace

Concept Flow - Trie Search Operation

Start at root node

↓

For each character in word

↓

Check if child node for character exists

Yes No↓

Move to child

↓

Repeat for next character

↓

After last char, check isEnd flag

Yes No↓

Word found

Start from root, follow nodes for each character. If any character node missing, word not found. If all 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++) {
    if (!current->children[word[i] - 'a']) return false;
    current = current->children[word[i] - 'a'];
  }
  return current->isEnd;
}

Searches for a word in the trie by traversing nodes for each character and checking end flag.

Execution Table

Step	Operation	Character	Node Exists?	Pointer Move	Trie State Visual
1	Start at root	-	N/A	current = root	root ├─ a: node ├─ b: node └─ c: node
2	Check 'c'	c	Yes	current = node for 'c'	root ├─ a: node ├─ b: node └─ c: current
3	Check 'a'	a	Yes	current = node for 'a'	root ├─ a: node ├─ b: node └─ c └─ a: current
4	Check 't'	t	Yes	current = node for 't'	root ├─ a: node ├─ b: node └─ c └─ a └─ t: current
5	End of word	-	N/A	Check isEnd flag	current node isEnd = true
6	Result	-	-	-	Word 'cat' found (true)

💡 Traversal ended after last character; isEnd flag true means word found

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
current	root	node for 'c'	node for 'a' under 'c'	node for 't' under 'a'	node for 't' under 'a'

Key Moments - 3 Insights

Why do we check if the child node exists before moving current pointer?

Because if the child node for a character does not exist (see Step 2-4 in execution_table), the word cannot be in the trie, so we stop searching immediately.

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

Because nodes can represent prefixes too. Only if isEnd is true at the last character node (Step 5), the full word exists in the trie.

What happens if the word is empty (zero length)?

The search returns true only if the root node's isEnd flag is true, meaning empty string is stored. Otherwise, false.

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'current' pointer after Step 3?

A Node for 't' under 'a'

B Root node

C Node for 'a' under 'c'

D Node for 'c' under root

💡 Hint

Check 'Pointer Move' column at Step 3 in execution_table

At which step does the search confirm the word is found?

A Step 5

B Step 6

C Step 2

D Step 4

💡 Hint

Look at the 'Result' row in execution_table

If the node for character 't' was missing, what would happen?

A Search returns false at Step 4

B Search continues to next character

C Search returns true immediately

D Search restarts from root

💡 Hint

Refer to 'Node Exists?' and 'Operation' columns in execution_table Steps 2-4

Concept Snapshot

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

Full Transcript

Trie search starts at the root node. For each character in the word, it checks if a child node exists. If yes, it moves the current pointer to that child node. If any character node is missing, the search stops and returns false. After all characters are found, it checks the isEnd flag of the last node. If true, the word exists in the trie; otherwise, it does not. This process ensures efficient prefix-based search.

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