Prefix Search Using Trie in DSA C# - Execution Trace

Concept Flow - Prefix Search Using Trie

Start at root node

↓

For each char in prefix

↓

Check if char child exists?

No→Prefix not found

Yes↓

Move to child node

↓

After last char

↓

Collect all words from this node

↓

Return list of words

Start from root, follow each prefix character down the trie nodes. If path exists, collect all words below that node.

Execution Sample

DSA C#

Insert("cat")
Insert("car")
Insert("dog")
SearchPrefix("ca")

Insert words 'cat', 'car', 'dog' into trie, then search for words starting with prefix 'ca'.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat'	root -> c -> a -> t	root.children['c'] created c.children['a'] created a.children['t'] created	root └─ c └─ a └─ t*
2	Insert 'car'	root -> c -> a -> t, r	c.children['a'] exists a.children['r'] created	root └─ c └─ a ├─ t* └─ r*
3	Insert 'dog'	root -> c -> a -> t, r; d -> o -> g	root.children['d'] created d.children['o'] created o.children['g'] created	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d └─ o └─ g*
4	Search prefix 'ca'	root -> c -> a -> t, r; d -> o -> g	Traverse root -> c -> a	At node 'a': collect words 'cat', 'car'
5	Return words with prefix 'ca'	No change	No pointer change	Output: ['cat', 'car']

💡 Prefix traversal ends after last prefix character 'a'; words collected from that node.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
Trie Nodes	root (empty)	root -> c -> a -> t*	root -> c -> a -> t*, r*	root -> c -> a -> t*, r*; d -> o -> g*	Same as after step 3	Same as after step 3
Current Node (during search)	root	N/A	N/A	N/A	node 'a'	node 'a'
Collected Words	[]	N/A	N/A	N/A	['cat', 'car']	['cat', 'car']

Key Moments - 3 Insights

Why do we create new nodes only when the character path doesn't exist?

Because existing nodes represent shared prefixes. See execution_table steps 1 and 2 where 'c' and 'a' nodes are reused for 'car' after 'cat' insertion.

How do we know when to stop traversing during prefix search?

We stop after processing all prefix characters. In execution_table step 4, traversal stops at node 'a' after 'c' and 'a' are found.

How are words collected after reaching the prefix node?

We collect all words in the subtree rooted at the prefix node. Step 4 shows collecting 'cat' and 'car' from node 'a'.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, which new node is created?

A Node 't' as child of 'a'

B Node 'r' as child of 'a'

C Node 'd' as child of root

D Node 'o' as child of 'd'

💡 Hint

Check Pointer Changes column at step 2 in execution_table

At which step does the prefix search traversal end?

A Step 4

B Step 3

C Step 5

D Step 1

💡 Hint

Look at Operation and Pointer Changes columns in execution_table

If we search prefix 'do', which node will be the current node after traversal?

A Node 'd'

B Node 'g'

C Node 'o'

D Root node

💡 Hint

Follow the prefix characters in variable_tracker Current Node row

Concept Snapshot

Prefix Search Using Trie:
- Start at root node
- For each prefix char, move to child node if exists
- If any char missing, prefix not found
- After last char, collect all words below
- Returns list of words starting with prefix

Full Transcript

This visual trace shows how prefix search works in a trie. We insert words 'cat', 'car', and 'dog' step by step, creating nodes only when needed. Then we search for prefix 'ca' by traversing nodes 'c' and 'a'. Once at node 'a', we collect all words below it, which are 'cat' and 'car'. The execution table tracks the trie nodes, pointer changes, and visual state after each operation. Variable tracker shows how the trie structure and current node change over time. Key moments clarify why nodes are reused, when traversal stops, and how words are collected. The quiz tests understanding of node creation, traversal stopping, and current node after prefix search.

Practice

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

easy

A. To perform arithmetic operations quickly

B. To sort words alphabetically

C. To efficiently find all words that start with a given prefix

D. To store numbers in sorted order

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie stores words in a tree-like structure where each node represents a character. This allows quick traversal to find words sharing the same prefix.

2. Step 2: Identify the main use case

   Because of this structure, Tries are mainly used to find all words starting with a given prefix efficiently.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option C

4. Quick Check:

   Trie = prefix search efficiency [OK]

Hint: Trie nodes represent characters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie is for arithmetic operations
• Assuming Trie stores numbers only

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

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

C. public class TrieNode { public int[] Children = new int[26]; public bool IsEndOfWord; }

D. public class TrieNode { public string Children; public bool IsEndOfWord; }

Solution

1. Step 1: Identify the correct data type for children nodes

   Trie nodes store children as a map from characters to TrieNode objects. Dictionary is the correct choice in C#.

2. Step 2: Check the other options

   List<int> or int[] are incorrect because they don't map characters to nodes. String is also incorrect as children must be nodes, not strings.

3. Final Answer:

   public class TrieNode { public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>(); public bool IsEndOfWord; } -> Option A

4. Quick Check:

   Children map chars to nodes = public class TrieNode { public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>(); public bool IsEndOfWord; } [OK]

Hint: Use Dictionary for children in C# TrieNode [OK]

Common Mistakes:

• Using List<int> instead of Dictionary
• Using array of ints instead of nodes
• Declaring children as string

3. What will be the output of the following C# code snippet?

var trie = new Trie();
trie.Insert("cat");
trie.Insert("car");
trie.Insert("dog");
var result = trie.SearchPrefix("ca");
Console.WriteLine(string.Join(",", result));

Assuming SearchPrefix returns all words starting with the given prefix.

medium

A. cat,car

B. dog

C. cat

D. car,dog

Solution

1. Step 1: Insert words into the Trie

   The words "cat", "car", and "dog" are inserted. "cat" and "car" share the prefix "ca".

2. Step 2: Search for prefix "ca"

   Searching prefix "ca" returns all words starting with "ca", which are "cat" and "car".

3. Final Answer:

   cat,car -> Option A

4. Quick Check:

   Words with prefix "ca" = cat,car [OK]

Hint: SearchPrefix returns all words starting with given prefix [OK]

Common Mistakes:

• Returning only one word instead of all matches
• Confusing prefix "ca" with "car"
• Including words without the prefix

4. The following C# method is intended to check if a prefix exists in a Trie. What is the bug?

public bool StartsWith(string prefix) {
    var node = root;
    foreach (var ch in prefix) {
        if (!node.Children.ContainsKey(ch))
            return false;
        node = node.Children[ch];
    }
    return node.IsEndOfWord;
}

medium

A. It should return false if prefix is empty

B. It should check for null before accessing Children

C. It should use a while loop instead of foreach

D. It should return true after traversing prefix, not check IsEndOfWord

Solution

1. Step 1: Understand method purpose

   The method checks if any word in the Trie starts with the given prefix.

2. Step 2: Identify the bug in return statement

   Returning node.IsEndOfWord checks if prefix itself is a complete word, but prefix search should return true if prefix exists regardless of word end.

3. Final Answer:

   It should return true after traversing prefix, not check IsEndOfWord -> Option D

4. Quick Check:

   Prefix exists if traversal succeeds, no need to check IsEndOfWord [OK]

Hint: Prefix check returns true if traversal succeeds, ignore IsEndOfWord [OK]

Common Mistakes:

• Checking IsEndOfWord for prefix existence
• Not handling empty prefix correctly
• Using wrong loop type

5. You want to implement a method GetAllWordsWithPrefix in a Trie that returns all words starting with a given prefix. Which approach correctly combines prefix traversal and word collection?

hard

A. Return words only if prefix is a complete word in Trie

B. Traverse to prefix node, then recursively collect all words from that node

C. Collect all words in Trie, then filter those starting with prefix

D. Traverse Trie nodes randomly and collect words

Solution

1. Step 1: Traverse Trie to prefix node

   First, move down the Trie following the prefix characters to reach the node representing the last prefix character.

2. Step 2: Recursively collect all words from prefix node

   From this node, recursively explore all child nodes to collect complete words that start with the prefix.

3. Final Answer:

   Traverse to prefix node, then recursively collect all words from that node -> Option B

4. Quick Check:

   Prefix traversal + recursion = Traverse to prefix node, then recursively collect all words from that node [OK]

Hint: Find prefix node first, then gather words recursively [OK]

Common Mistakes:

• Filtering all words after collecting entire Trie
• Returning words only if prefix is a full word
• Random traversal without prefix focus