Word Search in Trie in DSA C# - Execution Trace

Concept Flow - Word Search in Trie

Start at root node

↓

For each character in word

↓

Check if character child exists

↓

Move to child

↓

After last char, check isWord flag

↓

Word found

Start from the root and check each character in the word. Move down the trie nodes if the character exists. If all characters are found and the last node marks a word end, the word exists.

Execution Sample

DSA C#

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

Insert words 'cat' and 'car' into the trie, then search for 'car' and print if found.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat' - add 'c'	root	root.children['c'] created	root -> c
2	Insert 'cat' - add 'a'	root -> c	c.children['a'] created	root -> c -> a
3	Insert 'cat' - add 't'	root -> c -> a	a.children['t'] created, mark 't' as word end	root -> c -> a -> t*
4	Insert 'car' - 'c' exists	root -> c -> a -> t*	move to c	root -> c -> a -> t*
5	Insert 'car' - 'a' exists	root -> c -> a -> t*	move to a	root -> c -> a -> t*
6	Insert 'car' - add 'r'	root -> c -> a -> t*	a.children['r'] created, mark 'r' as word end	root -> c -> a -> t*, r*
7	Search 'car' - check 'c'	root -> c -> a -> t*, r*	move to c	root -> c -> a -> t*, r*
8	Search 'car' - check 'a'	root -> c -> a -> t*, r*	move to a	root -> c -> a -> t*, r*
9	Search 'car' - check 'r'	root -> c -> a -> t*, r*	move to r	root -> c -> a -> t*, r*
10	Check isWord at 'r'	root -> c -> a -> t*, r*	isWord true, word found	root -> c -> a -> t*, r*

💡 Search ends after last character 'r' found and isWord flag is true.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	After Step 10
Current Node	root	c node	t node	r node	r node
Trie Size (words)	0	0	1 ('cat')	2 ('cat', 'car')	2 ('cat', 'car')
Word Found Flag	false	false	false	false	true

Key Moments - 3 Insights

Why do we check the isWord flag after the last character?

Because nodes can be shared prefixes, the isWord flag tells if the path forms a complete word. See execution_table step 10 where 'r' node's isWord is true, confirming 'car' exists.

What happens if a character is missing during search?

The search stops immediately and returns false. In the flow, if a child node for a character doesn't exist (No branch), the word is not found.

Why do we create new nodes only when inserting?

Because existing nodes represent prefixes already stored. New nodes are created only for new characters. See execution_table steps 1-3 for 'cat' insertion and steps 4-6 for 'car' insertion.

Visual Quiz - 3 Questions

Look at the execution_table, what node is the current node after step 3?

A Node 'c'

B Node 'a'

C Node 't'

D Root node

💡 Hint

Check the 'Pointer Changes' and 'Nodes in Trie' columns at step 3.

At which step does the trie mark the end of the word 'car'?

A Step 3

B Step 6

C Step 9

D Step 10

💡 Hint

Look for 'mark 'r' as word end' in the 'Pointer Changes' column.

If we search for 'cap', at which step would the search fail?

A After checking 'p'

B After checking 'c'

C After checking 'a'

D At the root node

💡 Hint

Refer to the concept_flow where missing child node causes search to stop.

Concept Snapshot

Trie Word Search:
- Start at root node
- For each char, move to child node if exists
- If missing child, word not found
- After last char, check isWord flag
- True means word exists, else not

Full Transcript

This visual trace shows how to search a word in a trie. We start at the root node and check each character of the word one by one. If the character exists as a child node, we move down to that node. If at any point the character is missing, the search stops and the word is not found. After checking all characters, we look at the isWord flag on the last node. If it is true, the word exists in the trie. The example inserts 'cat' and 'car', then searches for 'car', confirming it is found.

Practice

1. What is the main purpose of using a Trie data structure in word search problems?

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To store words in a linked list

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 in word search

   It allows quick prefix-based search, making it efficient to find words starting with given letters.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie stores words linearly
• Assuming Trie is for arithmetic

2. Which of the following is the correct way to declare a Trie node class in C#?

easy

A. public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsWordEnd = false; }

B. public class TrieNode { public List<int> Children; public bool IsWordEnd; }

C. public class TrieNode { public string Children; public int IsWordEnd; }

D. public class TrieNode { public int Children; public bool IsWordEnd; }

Solution

1. Step 1: Check data types for children

   Trie children should map characters to TrieNode objects, so Dictionary is correct.

2. Step 2: Check word end marker

   Boolean flag IsWordEnd indicates if node ends a word, so bool is correct type.

3. Final Answer:

   public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsWordEnd = false; } -> Option A

4. Quick Check:

   Children dictionary + bool flag = public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsWordEnd = false; } [OK]

Hint: Trie node children map chars to nodes with bool end flag [OK]

Common Mistakes:

• Using List<int> instead of Dictionary
• Using string or int for children
• Using int instead of bool for IsWordEnd

3. Given the following C# code snippet for searching a word in a Trie, what will be the output?

Trie trie = new Trie();
trie.Insert("cat");
trie.Insert("car");
trie.Insert("dog");

bool result = trie.Search("cap");
Console.WriteLine(result);

medium

A. True

B. False

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Understand inserted words

   Words "cat", "car", and "dog" are inserted into the Trie.

2. Step 2: Search for "cap"

   "cap" shares prefix "ca" but 'p' is not inserted after 'a', so search returns false.

3. Final Answer:

   False -> Option B

4. Quick Check:

   Word not found = False [OK]

Hint: Search returns false if full word path missing [OK]

Common Mistakes:

• Assuming prefix match means word found
• Expecting true for partial matches
• Confusing compilation/runtime errors

4. Identify the error in the following C# Trie search method:

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 true;
}

medium

A. It does not check for null root

B. It throws NullReferenceException if word is empty

C. It returns true even if the word is only a prefix, not a complete word

D. It uses wrong data type for node

Solution

1. Step 1: Analyze search logic

   The method checks if all characters exist in Trie nodes but does not check if last node marks end of a word.

2. Step 2: Identify missing condition

   Without checking node.IsWordEnd, it returns true for prefixes that are not complete words.

3. Final Answer:

   It returns true even if the word is only a prefix, not a complete word -> Option C

4. Quick Check:

   Missing IsWordEnd check = It returns true even if the word is only a prefix, not a complete word [OK]

Hint: Always check IsWordEnd after traversal [OK]

Common Mistakes:

• Ignoring IsWordEnd flag
• Assuming prefix means word found
• Not handling empty strings

5. You want to find all words in a Trie that start with the prefix "pre". Which approach correctly uses the Trie to achieve this?

hard

A. Use a hash set to store all words and filter those starting with "pre"

B. Search each word in the Trie individually to check if it starts with "pre"

C. Insert all words starting with "pre" into a new Trie and search there

D. Traverse the Trie to the node representing 'e' in "pre", then perform a DFS to collect all words below

Solution

1. Step 1: Locate prefix node in Trie

   Traverse characters 'p', 'r', 'e' to reach the node representing last prefix character.

2. Step 2: Collect words using DFS

   From this node, perform depth-first search to find all complete words that start with "pre".

3. Final Answer:

   Traverse the Trie to the node representing 'e' in "pre", then perform a DFS to collect all words below -> Option D

4. Quick Check:

   Prefix node + DFS = Traverse the Trie to the node representing 'e' in "pre", then perform a DFS to collect all words below [OK]

Hint: Find prefix node, then DFS for words [OK]

Common Mistakes:

• Checking all words individually
• Using unrelated data structures
• Rebuilding Trie unnecessarily