Prefix Search Using Trie in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths from the root to nodes represent prefixes of words.

beginner

How does a Trie help in prefix search?

A Trie allows quick prefix search by following the path of characters from the root node. If the prefix exists, the search reaches the node representing the last character of the prefix, from which all words with that prefix can be found.

intermediate

What is the time complexity of searching a prefix in a Trie?

The time complexity is O(m), where m is the length of the prefix. This is because we traverse one node per character in the prefix.

beginner

In a Trie node, what does the 'children' array or dictionary represent?

The 'children' represent links to the next characters in the stored words. Each child corresponds to a possible next character from the current node.

beginner

What is the purpose of the 'isEndOfWord' flag in a Trie node?

The 'isEndOfWord' flag marks that the path from the root to this node forms a complete word stored in the Trie.

What does each node in a Trie represent?

A A whole word

B A character of a word

C A number

D A prefix length

Each node in a Trie represents a single character of a word.

What is the main advantage of using a Trie for prefix search?

A Faster prefix lookup by character traversal

B Uses less memory than arrays

C Sorts words automatically

D Stores only numbers

Trie allows fast prefix lookup by traversing nodes for each character.

If a prefix is not found in a Trie, what does that mean?

A No word in the Trie starts with that prefix

B All words start with that prefix

C The Trie is empty

D The prefix is a complete word

If prefix path is missing, no word in the Trie starts with that prefix.

What does the 'isEndOfWord' flag indicate in a Trie node?

A The node is the root

B The node is a prefix only

C The node has no children

D The node marks the end of a stored word

'isEndOfWord' means the path to this node forms a complete word.

What is the time complexity to insert a word of length n into a Trie?

A O(n^2)

B O(1)

C O(n)

D O(log n)

Insertion requires traversing or creating nodes for each character, so O(n).

Explain how prefix search works using a Trie data structure.

Think about following characters step-by-step in the tree.

Describe the structure of a Trie node and its role in prefix search.

Focus on what each node stores and how it connects.

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