Autocomplete System with Trie in DSA C#

Mental Model

A Trie stores words by sharing common prefixes so we can quickly find all words starting with a given prefix.

Analogy: Imagine a tree where each branch is a letter, and paths from the root to leaves form words. To autocomplete, you follow the prefix branches and then list all words below.

root
 ↓
 t -> r -> i -> e -> [end]
  ↓
  r -> e -> e -> [end]
  ↓
  y -> [end]

Dry Run Walkthrough

Input: Insert words: "tree", "trie", "try"; autocomplete prefix: "tr"

Goal: Find all words starting with "tr" using the Trie

Step 1: Insert 'tree' letter by letter into the Trie

root -> t -> r -> e -> e -> [end]

Why: We add nodes for each letter to build the word path

Step 2: Insert 'trie' sharing prefix 'tr', add new nodes for 'i' and 'e'

root -> t -> r -> e -> e -> [end]
           ↓
           i -> e -> [end]

Why: Reuse existing prefix nodes to save space and time

Step 3: Insert 'try' sharing prefix 'tr', add new node for 'y'

root -> t -> r -> e -> e -> [end]
           ↓       ↓
           i -> e -> [end]  y -> [end]

Why: Add new branch for different word ending

Step 4: Search for prefix 'tr' by following nodes t -> r

[prefix found at node r]
root -> t -> r -> ...

Why: Locate the node where prefix ends to start autocomplete

Step 5: Collect all words below node 'r': 'tree', 'trie', 'try'

Words found: tree, trie, try

Why: Gather all completions starting with prefix

Result:

root -> t -> r -> e -> e -> [end]
           ↓       ↓
           i -> e -> [end]  y -> [end]
Autocomplete results: tree, trie, try

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class TrieNode
{
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsWordEnd = false;
}

class Trie
{
    private TrieNode root = new TrieNode();

    public void Insert(string word)
    {
        TrieNode curr = root;
        foreach (char c in word)
        {
            if (!curr.Children.ContainsKey(c))
                curr.Children[c] = new TrieNode();
            curr = curr.Children[c]; // advance curr to next node
        }
        curr.IsWordEnd = true; // mark end of word
    }

    public List<string> Autocomplete(string prefix)
    {
        TrieNode curr = root;
        foreach (char c in prefix)
        {
            if (!curr.Children.ContainsKey(c))
                return new List<string>(); // prefix not found
            curr = curr.Children[c]; // advance curr to prefix end
        }
        List<string> results = new List<string>();
        DFS(curr, prefix, results); // collect all words below prefix
        return results;
    }

    private void DFS(TrieNode node, string path, List<string> results)
    {
        if (node.IsWordEnd)
            results.Add(path); // found a complete word
        foreach (var kvp in node.Children)
            DFS(kvp.Value, path + kvp.Key, results); // explore children
    }
}

class Program
{
    static void Main()
    {
        Trie trie = new Trie();
        trie.Insert("tree");
        trie.Insert("trie");
        trie.Insert("try");

        List<string> completions = trie.Autocomplete("tr");
        foreach (string word in completions)
            Console.WriteLine(word);
    }
}

curr = curr.Children[c]; // advance curr to next node

advance curr to next node to build or traverse prefix

curr.IsWordEnd = true; // mark end of word

mark node as end of a valid word

if (!curr.Children.ContainsKey(c)) return new List<string>(); // prefix not found

stop if prefix path does not exist

DFS(curr, prefix, results); // collect all words below prefix

start depth-first search to find all completions

if (node.IsWordEnd) results.Add(path); // found a complete word

add word to results when end node reached

foreach (var kvp in node.Children) DFS(kvp.Value, path + kvp.Key, results); // explore children

recursively explore all child nodes to find words

Output

tree

trie

try

Complexity Analysis

Time: O(m + n) where m is length of prefix and n is total letters in all words below prefix because we traverse prefix then DFS all descendants

Space: O(n) for storing all nodes in the Trie and recursion stack during DFS

vs Alternative: Compared to scanning all words linearly (O(total words * average length)), Trie reduces prefix search to O(m) plus DFS on relevant subtree, making autocomplete faster

Edge Cases

Empty prefix

Returns all words stored in the Trie

DSA C#

if (!curr.Children.ContainsKey(c)) return new List<string>(); // prefix not found

Prefix not in Trie

Returns empty list immediately

DSA C#

if (!curr.Children.ContainsKey(c)) return new List<string>(); // prefix not found

Words with shared prefix

Trie shares nodes for prefix, saving space and time

DSA C#

if (!curr.Children.ContainsKey(c)) curr.Children[c] = new TrieNode();

When to Use This Pattern

When you need to quickly find all words starting with a prefix, use a Trie to share prefixes and speed up search.

Common Mistakes

Mistake: Not marking the end of a word, causing autocomplete to miss valid words
Fix: Set IsWordEnd = true at the last node of inserted word

Mistake: Not checking if prefix exists before DFS, causing errors or wrong results
Fix: Return empty list if prefix path is missing before DFS

Summary

Stores words in a tree structure sharing prefixes to enable fast autocomplete.

Use when you want to find all words starting with a given prefix efficiently.

The key is to follow prefix nodes then explore all child nodes to list completions.

Practice

1. What is the main advantage of using a Trie over a HashSet for implementing an autocomplete system?

easy

A. Trie uses less memory than HashSet for all cases

B. Trie supports prefix-based search efficiently, while HashSet requires checking all words

C. Trie is faster for exact word lookup than HashSet

D. Trie automatically sorts words alphabetically unlike HashSet

Solution

1. Step 1: Understand autocomplete requirement

   Autocomplete needs to find all words that start with a given prefix quickly.

2. Step 2: Compare Trie vs HashSet

   Trie stores characters level by level, so prefix traversal is O(prefix length). HashSet requires scanning all words to check which ones start with the prefix.

3. Final Answer:

   Trie supports prefix-based search efficiently, while HashSet requires checking all words -> Option B

4. Quick Check:

   Trie = prefix search in O(m), HashSet = O(n*m) for prefix [OK]

Hint: Trie shares common prefixes among words - natural fit for autocomplete [OK]

Common Mistakes:

• Assuming Trie always uses less memory - it can use more for sparse word sets
• Thinking exact lookup is why Trie beats HashSet - HashSet is actually faster for exact lookup
• Assuming Trie sorts automatically - it doesn't sort, traversal order depends on children insertion

2. Which C# code correctly inserts a word into a Trie node structure where each node has a Dictionary<char, TrieNode> Children and a bool IsEndOfWord?

easy

A. node.Children[c] = new TrieNode(); node = node.Children[c];

B. if (!node.Children.ContainsKey(c)) node.Children[c] = new TrieNode(); node = node.Children[c];

C. node.Children.Add(c); node = node.Children[c];

D. node.Children[c] = c; node = node.Children[c];

Solution

1. Step 1: Check if child exists

   Before creating a new node, check if the character key already exists in Children to avoid overwriting existing subtrees.

2. Step 2: Create only if missing

   Using ContainsKey check ensures we reuse existing nodes and only create new ones when the character path doesn't exist yet.

3. Final Answer:

   if (!node.Children.ContainsKey(c)) node.Children[c] = new TrieNode(); node = node.Children[c]; -> Option B

4. Quick Check:

   Always check ContainsKey before adding to avoid overwriting existing paths [OK]

Hint: Always guard with ContainsKey before inserting a new Trie node [OK]

Common Mistakes:

• Option A overwrites existing children, destroying previously inserted words
• Option C uses Add which throws if key already exists
• Option D stores char as value instead of TrieNode

3. What will the following C# Trie prefix search return when searching for prefix "ca" in a Trie containing ["cat", "car", "card", "dog"]?

List<string> results = new List<string>();
void DFS(TrieNode node, string current) {
    if (node.IsEndOfWord) results.Add(current);
    foreach (var kvp in node.Children)
        DFS(kvp.Value, current + kvp.Key);
}
TrieNode prefixNode = GetPrefixNode("ca");
if (prefixNode != null) DFS(prefixNode, "ca");

medium

A. ["cat", "car", "card", "dog"]

B. ["ca"]

C. ["cat", "car", "card"]

D. []

Solution

1. Step 1: Find prefix node

   GetPrefixNode("ca") traverses c→a and returns the node at 'a'. "dog" is unreachable from this node.

2. Step 2: DFS from prefix node

   DFS explores all children from 'a': t (cat), r (car), r→d (card). All three have IsEndOfWord=true.

3. Final Answer:

   ["cat", "car", "card"] -> Option C

4. Quick Check:

   Only words under prefix "ca" subtree are returned, "dog" excluded [OK]

Hint: DFS from prefix node returns only words in that subtree - "dog" is in a different branch [OK]

Common Mistakes:

• Including 'dog' - it's in a completely separate Trie branch
• Returning only 'ca' - 'ca' itself is not marked IsEndOfWord
• Returning empty - prefix 'ca' exists in the Trie so DFS finds words

4. Identify the bug in this C# autocomplete prefix search:

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

medium

A. Should return false when character not found, and true at the end

B. Should use a List instead of Dictionary for Children

C. Should check IsEndOfWord instead of ContainsKey

D. Should start from the last character of the prefix

Solution

1. Step 1: Trace the logic

   When a character is not found in Children, it means the prefix doesn't exist - should return false, not true. And after traversing all prefix characters successfully, the prefix exists - should return true.

2. Step 2: Identify the swap

   The return values are swapped: 'return true' and 'return false' are in each other's place.

3. Final Answer:

   Should return false when character not found, and true at the end -> Option A

4. Quick Check:

   Missing prefix char = false, full prefix traversed = true [OK]

Hint: If you can't follow the path, prefix is absent = false; if path complete = true [OK]

Common Mistakes:

• Thinking Dictionary is wrong - Dictionary is correct for Children
• Checking IsEndOfWord - StartsWith only checks if prefix path exists, not word end
• Starting from last character - prefix traversal always goes left to right

5. In a Trie-based autocomplete system with 100,000 words averaging 8 characters each, what is the time complexity to retrieve all words matching a prefix of length p, where k is the number of matching words and m is the average word length?

hard

A. O(n) where n is total number of words

B. O(p + k * m) - traverse prefix then DFS over matching words

C. O(p * n) - check prefix against each word

D. O(1) - Trie provides constant time autocomplete

Solution

1. Step 1: Cost of reaching prefix node

   Traversing p characters to reach the prefix node costs O(p).

2. Step 2: Cost of DFS to collect results

   DFS visits all nodes under the prefix subtree. With k matching words of average length m, this costs O(k * m) in the worst case.

3. Final Answer:

   O(p + k * m) -> Option B

4. Quick Check:

   Prefix traversal O(p) + result collection O(k*m) = O(p + k*m) [OK]

Hint: Trie autocomplete = prefix path O(p) + collect results O(k*m), independent of total word count n [OK]

Common Mistakes:

• O(n) - Trie doesn't scan all words, only the prefix subtree
• O(1) - result collection depends on number and length of matching words
• O(p*n) - that's the HashSet approach, not Trie