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?

No→Word NOT found

Yes↓

Move to child node

↓

All characters processed?

No→Repeat for next character

Yes↓

Check if current node marks end of word?

↓

Yes: Word FOUND

The search starts at the root and moves through child nodes for each character. If any character node is missing, the word is not found. If all characters are found and the last node marks word end, the word exists.

Execution Sample

DSA C#

bool Search(string word) {
  TrieNode current = root;
  foreach (char c in word) {
    if (!current.children.ContainsKey(c)) return false;
    current = current.children[c];
  }
  return current.isEndOfWord;
}

This code checks each character of the word in the trie nodes. If all characters are found and the last node marks the end of a word, it returns true.

Execution Table

Step	Operation	Current Character	Node Exists?	Pointer Changes	Visual State
1	Start at root	-	N/A	current = root	root (no char)
2	Check 'c'	'c'	Yes	current = root.children['c']	root → c
3	Check 'a'	'a'	Yes	current = c.children['a']	root → c → a
4	Check 't'	't'	Yes	current = a.children['t']	root → c → a → t
5	All chars processed	-	-	-	At node 't' (isEndOfWord = true)
6	Return result	-	-	-	Word FOUND (true)
7	Search for 'car'	-	-	-	Start at root
8	Check 'c'	'c'	Yes	current = root.children['c']	root → c
9	Check 'a'	'a'	Yes	current = c.children['a']	root → c → a
10	Check 'r'	'r'	No	-	No node for 'r' under 'a'
11	Return result	-	-	-	Word NOT found (false)

💡 Search stops when a character node is missing or all characters are found and end of word is checked.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 8	After Step 9	After Step 10	Final
current	root	node 'c'	node 'a'	node 't'	node 't'	node 'c'	node 'a'	null	null
current.isEndOfWord	false	false	false	true	true	false	false	N/A	N/A

Key Moments - 3 Insights

Why does the search return false immediately when a character node is missing?

Because the trie does not contain that character path, so the word cannot be present. This is shown in execution_table row 10 where 'r' node is missing under 'a', so search stops.

Why do we check isEndOfWord after processing all characters?

Because a path may exist for all characters but not mark a complete word. For example, 'cat' is found only if the last node marks end of word (row 5). Otherwise, it's just a prefix.

What happens to the current pointer when moving through the trie?

The current pointer moves from root to each child node matching the character. This is tracked in variable_tracker showing current moving from root to 'c', then 'a', then 't'.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the current node's character?

A 'c'

B 't'

C 'a'

D root

💡 Hint

Check the 'Current Character' and 'Pointer Changes' columns at step 4 in execution_table.

At which step does the search fail for the word 'car'?

A Step 10

B Step 9

C Step 11

D Step 8

💡 Hint

Look at the 'Node Exists?' column for 'r' character in execution_table.

If the word searched was 'ca', what would be the final check in the search?

A Check if root is end of word

B Check if node 'c' is end of word

C Check if node 'a' is end of word

D No check needed, word found

💡 Hint

Refer to the concept_flow and execution_table steps for end of word check after all characters.

Concept Snapshot

Trie Search Operation:
- Start at root node
- For each character, move to child node if exists
- If any character node missing, return false
- After last character, check isEndOfWord flag
- Return true if end of word, else false

Full Transcript

Trie search starts at the root node and checks each character of the word one by one. For each character, it moves to the corresponding child node if it exists. If at any point a character node is missing, the search stops and returns false, meaning the word is not in the trie. If all characters are found, the search checks if the last node marks the end of a word. If yes, it returns true, confirming the word exists. Otherwise, it returns false, indicating the word is only a prefix but not a complete word in the trie.

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. Inserts a new word into the Trie

C. Deletes a word from 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 data 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:

   Search = Check word presence [OK]

Hint: Search checks presence, 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 C# method signature for a Trie search operation that returns a boolean?

easy

A. public void Search(string word)

B. public bool Search(string word)

C. public int Search(string word)

D. public string Search(string word)

Solution

1. Step 1: Identify return type for search

   Search should return true or false indicating if the word exists, so return type must be bool.

2. Step 2: Check method signature correctness

   Method takes a string parameter for the word and returns bool, matching "public bool Search(string word)".

3. Final Answer:

   public bool Search(string word) -> Option B

4. Quick Check:

   Search returns bool for word presence [OK]

Hint: Search returns true/false, so return type is bool [OK]

Common Mistakes:

• Using void return type for search
• Returning int or string instead of bool
• Incorrect method parameter types

3. Given the following Trie search code snippet, what will be the output when searching for the word "cat" after inserting "car" and "cat"?

Trie trie = new Trie();
trie.Insert("car");
trie.Insert("cat");
Console.WriteLine(trie.Search("cat"));
Console.WriteLine(trie.Search("cap"));

medium

A. False
True

B. True
True

C. True
False

D. False
False

Solution

1. Step 1: Analyze inserted words

   Words "car" and "cat" are inserted, so both exist in the Trie.

2. Step 2: Check search results for "cat" and "cap"

   "cat" exists, so search returns true; "cap" was not inserted, so search returns false.

3. Final Answer:

   True False -> Option C

4. Quick Check:

   Search("cat")=True, Search("cap")=False [OK]

Hint: Inserted words return true; others return false [OK]

Common Mistakes:

• Assuming "cap" exists after inserting "car" and "cat"
• Mixing output order
• Confusing true/false outputs

4. Identify the bug in this Trie search method that causes it to always return false:

public bool Search(string word) {
    TrieNode node = root;
    foreach (char c in word) {
        if (!node.Children.ContainsKey(c))
            return false;
        node = node.Children[c];
    }
    return false;
}

medium

A. The method should return true immediately after first character check

B. It should return false if node.Children contains the character

C. The foreach loop should iterate over node.Children keys

D. It should return true after checking all characters if node marks end of word

Solution

1. Step 1: Understand the search logic

   The method checks each character in the word exists in the Trie nodes.

2. Step 2: Identify the missing return condition

   After the loop, it always returns false instead of checking if the current node marks the end of a valid word.

3. Final Answer:

   It should return true after checking all characters if node marks end of word -> Option D

4. Quick Check:

   Return true if end of word reached [OK]

Hint: Return true only if end of word node reached [OK]

Common Mistakes:

• Returning false unconditionally after loop
• Not checking end of word flag
• Returning true too early

5. You want to modify a Trie search operation to support prefix search (checking if any word starts with a given prefix). Which change is correct?

hard

A. Return true as soon as all prefix characters are found, without checking end of word

B. Return true only if the prefix is also a complete word in the Trie

C. Return false if any character in prefix is found

D. Return true only if prefix length equals word length

Solution

1. Step 1: Understand prefix search goal

   Prefix search should confirm if the Trie contains any word starting with the given prefix.

2. Step 2: Adjust search logic for prefix

   Return true immediately after all prefix characters are found, no need to check if prefix is a complete word.

3. Final Answer:

   Return true as soon as all prefix characters are found, without checking end of word -> Option A

4. Quick Check:

   Prefix found = true without full word check [OK]

Hint: Prefix search returns true once prefix path exists [OK]

Common Mistakes:

• Checking end of word for prefix search
• Returning false if prefix is not a full word
• Confusing prefix search with full word search