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 exists for char?

No→Word NOT found

Yes↓

Move to child node

↓

All chars processed?

No→Repeat for next char

Yes↓

Check if current node marks end of word?

↓

Yes

→Word FOUND

↓

No

→Word NOT found

The search starts at the root and checks each character's child node. If any character is missing, search fails. If all characters are found, it checks if the last node marks the end of a word.

Execution Sample

DSA C++

bool search(string word) {
  TrieNode* current = root;
  for (char c : word) {
    if (!current->children[c - 'a']) return false;
    current = current->children[c - 'a'];
  }
  return current->isEndOfWord;
}

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

Execution Table

Step	Operation	Current Character	Child Exists?	Pointer Movement	Trie State Visual
1	Start search at root	-	N/A	current = root	root └─ c └─ a └─ t
2	Check first char 'c'	c	Yes	current = current->children['c' - 'a']	root └─ c └─ a └─ t
3	Check second char 'a'	a	Yes	current = current->children['a' - 'a']	root └─ c └─ a └─ t
4	Check third char 't'	t	Yes	current = current->children['t' - 'a']	root └─ c └─ a └─ t (endOfWord)
5	All chars processed, check endOfWord	-	N/A	N/A	Node 't' marks end of word: TRUE
6	Return result	-	N/A	N/A	Word FOUND

💡 Search ends after all characters are found and endOfWord is true, confirming the word exists.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
current	root	node for 'c'	node for 'a'	node for 't'	node for 't'
current->children[c - 'a']	N/A	exists	exists	exists	N/A
current->isEndOfWord	false	false	false	true	true

Key Moments - 3 Insights

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

Because if the child node for the current character does not exist, it means the word is not in the trie, so we must stop searching immediately.

Why do we check if the current node marks end of word after processing all characters?

Because a path may exist for all characters, but only nodes marked as endOfWord represent complete words. Step 5 shows this check to confirm the word exists.

What happens if the word is a prefix but not a complete word in the trie?

The search will find all characters but current->isEndOfWord will be false (Step 5), so the word is considered not found.

Visual Quiz - 3 Questions

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

A Node for character 'c'

B Root node

C Node for character 'a'

D Node for character 't'

💡 Hint

Check the 'Pointer Movement' and 'Current Character' columns at Step 3 in execution_table.

At which step does the search confirm the word exists in the trie?

A Step 5

B Step 4

C Step 2

D Step 6

💡 Hint

Look at the 'Operation' and 'Trie State Visual' columns in execution_table for the endOfWord check.

If the child node for a character does not exist, what happens according to the execution flow?

A Search continues to next character

B Search returns false immediately

C Search marks endOfWord true

D Search restarts from root

💡 Hint

Refer to the concept_flow where the 'Child Exists?' check leads to 'Word NOT found' if No.

Concept Snapshot

Trie Search Operation:
- Start at root node
- For each character, move to child node if exists
- If any child missing, word not found
- After all chars, check if node marks end of word
- Return true if endOfWord is true, else false

Full Transcript

The trie search operation begins at the root node. For each character in the word, it checks if a child node exists. If a child node is missing, the search stops and returns false, meaning the word is not found. If all characters are found, it checks if the last node marks the end of a word. If yes, the search returns true, confirming the word exists in the trie. This process ensures only complete words are recognized, not just prefixes.

Practice

1. What does the search operation in a Trie data structure do?

easy

A. Checks if a given word exists in the Trie

B. Deletes a word from the Trie

C. Inserts a new word into the Trie

D. Counts the total words stored in the Trie

Solution

1. Step 1: Understand the purpose of search in Trie

   The search operation is designed to check if a specific word is present in the Trie structure.

2. Step 2: Differentiate from other operations

   Insertion adds words, deletion removes words, and counting totals words. Search only checks existence.

3. Final Answer:

   Checks if a given word exists in the Trie -> Option A

4. Quick Check:

   Trie search = check word presence [OK]

Hint: Search checks presence of word, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert operation
• Thinking search deletes words
• Assuming search counts words

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[ch])

B. if (node->children[ch] == nullptr)

C. if (node->children[ch] != nullptr)

D. if (node->children.find(ch) != node->children.end())

Solution

1. Step 1: Understand Trie children representation

   Trie children are usually stored in a map or unordered_map. To check existence, use find() method.

2. Step 2: Identify correct syntax for existence check

   Using find(ch) != end() confirms if character node exists without creating new nodes.

3. Final Answer:

   if (node->children.find(ch) != node->children.end()) -> Option D

4. Quick Check:

   Use find() to check key existence in map [OK]

Hint: Use find() != end() to check map key existence safely [OK]

Common Mistakes:

• Using node->children[ch] != nullptr causes insertion
• Accessing children[ch] directly creates new node
• Checking children[ch] == nullptr can cause insertion

3. Consider the following C++ Trie search code snippet:

bool search(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char ch : word) {
        if (node->children.find(ch) == node->children.end())
            return false;
        node = node->children[ch];
    }
    return node->isEndOfWord;
}

What will be the output of search(root, "cat") if the Trie contains words: "car", "cat", "cap"?

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Trace search for "cat" in Trie

   Each character 'c', 'a', 't' is found in children nodes. The loop completes without returning false.

2. Step 2: Check isEndOfWord flag at last node

   Since "cat" is inserted, the last node's isEndOfWord is true, so function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Word "cat" exists in Trie = true [OK]

Hint: If all chars found and isEndOfWord true, search returns true [OK]

Common Mistakes:

• Ignoring isEndOfWord flag and returning true prematurely
• Assuming partial match means word exists
• Confusing false return with missing character

4. Identify the bug in the following Trie search function:

bool search(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char ch : word) {
        if (node->children[ch] == nullptr)
            return false;
        node = node->children[ch];
    }
    return node->isEndOfWord;
}

medium

A. Missing check for empty word input

B. Using node->children[ch] in if condition inserts new nodes unintentionally

C. Incorrect return type for search function

D. Loop variable should be int, not char

Solution

1. Step 1: Analyze children access in if condition

   Accessing node->children[ch] creates a new node if it doesn't exist, which is wrong during search.

2. Step 2: Correct way to check existence

   Use find() method to check if child exists without creating new nodes.

3. Final Answer:

   Using node->children[ch] in if condition inserts new nodes unintentionally -> Option B

4. Quick Check:

   Accessing map key directly creates nodes [OK]

Hint: Use find() to check existence, not direct map access [OK]

Common Mistakes:

• Using direct map access in condition causing side effects
• Ignoring empty string edge case
• Wrong loop variable type

5. You have a Trie storing the words: "apple", "app", "application", "bat", "batch". Which of the following search queries will return false?

hard

A. "batch"

B. "app"

C. "appl"

D. "bat"

Solution

1. Step 1: Check if "appl" is a complete word in Trie

   "appl" is a prefix of "apple" and "application" but not a complete word, so isEndOfWord is false.

2. Step 2: Verify other words

   "app", "batch", and "bat" are all complete words stored in the Trie, so search returns true for them.

3. Final Answer:

   "appl" -> Option C

4. Quick Check:

   Prefix only, not full word = false [OK]

Hint: Search returns false for prefixes not marked as words [OK]

Common Mistakes:

• Assuming prefix is always found as word
• Ignoring isEndOfWord flag
• Confusing similar words with exact matches