Trie vs Hash Map for Prefix Matching in DSA C# - Trade-offs & Analysis

Mental Model

A trie stores words by shared prefixes in a tree, making prefix search fast. A hash map stores whole words as keys, so prefix search needs checking many keys.

Analogy: Imagine a phone book organized by first letters (trie) versus a pile of index cards sorted by full names (hash map). Finding all names starting with 'Jo' is quicker in the organized phone book.

Trie:
root
 ├─ j
 │   ├─ o
 │   │   ├─ h
 │   │   │   └─ n (end)
 │   │   └─ e
 │   │       └─ l (end)
Hash Map:
{ "john": value, "joel": value, "jane": value }

Dry Run Walkthrough

Input: words: ["john", "joel", "jane"], prefix: "jo"

Goal: Find all words starting with prefix "jo" using trie and hash map, compare steps

Step 1: Insert "john" into trie by creating nodes j -> o -> h -> n

root -> j -> o -> h -> n[end]

Why: Build trie nodes for each letter to represent the word

Step 2: Insert "joel" into trie by reusing j -> o and adding e -> l

root -> j -> o -> h -> n[end]
                  -> e -> l[end]

Why: Reuse common prefix nodes to save space and speed prefix search

Step 3: Insert "jane" into trie by creating new branch j -> a -> n -> e

root -> j -> o -> h -> n[end]
          │   -> e -> l[end]
          -> a -> n -> e[end]

Why: Add new branch for word with different prefix

Step 4: Search trie for prefix "jo" by following j -> o nodes

At node o, subtree contains h -> n[end], e -> l[end]

Why: Prefix found, collect all words below this node

Step 5: Collect words "john" and "joel" from trie subtree

Words found: "john", "joel"

Why: All words under prefix node are valid matches

Step 6: Search hash map keys for prefix "jo" by checking each key

Keys: "john", "joel", "jane"; matches: "john", "joel"

Why: Hash map requires scanning keys to find prefix matches

Result:

Trie structure:
root -> j -> o -> h -> n[end]
          │   -> e -> l[end]
          -> a -> n -> e[end]
Words with prefix 'jo': john, joel
Hash Map keys: {"john", "joel", "jane"}
Words with prefix 'jo': john, joel

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> SearchPrefix(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 word
        foreach (var kvp in node.Children)
            DFS(kvp.Value, path + kvp.Key, results); // explore children
    }
}

class Program
{
    static void Main()
    {
        string[] words = { "john", "joel", "jane" };
        string prefix = "jo";

        Trie trie = new Trie();
        foreach (string w in words)
            trie.Insert(w);

        List<string> trieResults = trie.SearchPrefix(prefix);

        // Hash map approach
        Dictionary<string, int> hashMap = new Dictionary<string, int>();
        foreach (string w in words)
            hashMap[w] = 1; // dummy value

        List<string> hashResults = new List<string>();
        foreach (string key in hashMap.Keys)
        {
            if (key.StartsWith(prefix))
                hashResults.Add(key); // check prefix match
        }

        Console.WriteLine("Trie results:");
        foreach (string w in trieResults)
            Console.WriteLine(w);

        Console.WriteLine("Hash map results:");
        foreach (string w in hashResults)
            Console.WriteLine(w);
    }
}

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

advance curr to next node -- build path for word

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

mark node as end of a valid word

curr = curr.Children[c]; // advance curr to prefix end

advance curr to node matching prefix

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

stop if prefix path missing

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

collect all words under prefix node

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

add word to results when end node reached

if (key.StartsWith(prefix)) hashResults.Add(key); // check prefix match

check each key for prefix match in hash map

Output

Trie results:

john

joel

Hash map results:

john

joel

Complexity Analysis

Time: Trie prefix search: O(m + k) where m is prefix length and k is number of matched words; Hash map prefix search: O(n * m) where n is number of keys and m is prefix length because each key is checked

Space: Trie uses O(total letters in all words) for nodes; Hash map uses O(n) for keys storage

vs Alternative: Trie is faster for prefix queries because it avoids scanning all keys; hash map is simpler but slower for prefix matching

Edge Cases

Empty word list

Trie and hash map return empty results without error

DSA C#

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

Prefix not present in any word

Both return empty list quickly

DSA C#

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

Words with shared prefix only

Trie reuses nodes efficiently; hash map still checks all keys

DSA C#

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

When to Use This Pattern

When a problem asks for fast prefix search or autocomplete, reach for the trie pattern because it stores words by shared prefixes enabling quick lookups.

Common Mistakes

Mistake: Using hash map keys directly for prefix search without scanning all keys
Fix: Implement scanning or use a trie to avoid full key scans

Mistake: Not marking end of word in trie nodes, causing incorrect results
Fix: Set IsWordEnd = true at the last node of each inserted word

Summary

Trie stores words in a tree by letters for fast prefix search; hash map stores whole words as keys requiring scanning.

Use trie when you need efficient prefix matching or autocomplete; use hash map for exact word lookups.

The key insight is that tries share prefixes in nodes, making prefix queries fast without checking all keys.

Practice

1. Which data structure is generally more efficient for prefix matching when dealing with a large set of strings?

easy

A. Array, because it stores elements in contiguous memory

B. Hash Map, because it stores keys and values with constant time lookup

C. Trie, because it stores prefixes explicitly and allows fast prefix searches

D. Linked List, because it allows sequential access

Solution

1. Step 1: Understand prefix matching requirements

   Prefix matching requires checking if a string starts with a given prefix efficiently.

2. Step 2: Compare Trie and Hash Map for prefix matching

   Trie stores prefixes explicitly, enabling fast prefix search. Hash Map is good for exact key lookup but not efficient for prefix queries.

3. Final Answer:

   Trie, because it stores prefixes explicitly and allows fast prefix searches -> Option C

4. Quick Check:

   Prefix matching = Trie [OK]

Hint: Trie stores prefixes explicitly, ideal for prefix search [OK]

Common Mistakes:

• Thinking hash map supports prefix search efficiently
• Confusing array or linked list with prefix matching
• Ignoring the need for prefix traversal

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

easy

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

B. public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord; }

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

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

Solution

1. Step 1: Identify the correct data type for children in TrieNode

   Children should map characters to TrieNode references, so Dictionary is appropriate.

2. Step 2: Check other options for correctness

   List<int> or int[] do not map characters to nodes directly; string is incorrect for children representation.

3. Final Answer:

   public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord; } -> Option B

4. Quick Check:

   TrieNode children = Dictionary [OK]

Hint: Trie children map chars to nodes using Dictionary [OK]

Common Mistakes:

• Using List<int> or int[] instead of Dictionary
• Using string type for children
• Not initializing the dictionary

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

var trie = new Trie();
trie.Insert("apple");
trie.Insert("app");
Console.WriteLine(trie.StartsWith("app"));
Console.WriteLine(trie.StartsWith("apl"));

Assuming Trie class has Insert and StartsWith methods implemented correctly.

medium

A. True
False

B. False
True

C. True
True

D. False
False

Solution

1. Step 1: Insert words "apple" and "app" into the Trie

   Both words share prefix "app", so Trie stores nodes for 'a', 'p', 'p', and further for 'l', 'e'.

2. Step 2: Check StartsWith("app") and StartsWith("apl")

   "app" is a prefix present in Trie, so returns True. "apl" is not a prefix of any inserted word, so returns False.

3. Final Answer:

   True False -> Option A

4. Quick Check:

   StartsWith("app")=True, StartsWith("apl")=False [OK]

Hint: Check if prefix exists exactly in Trie nodes [OK]

Common Mistakes:

• Assuming "apl" prefix exists
• Confusing Insert with StartsWith
• Mixing up True/False outputs

4. The following code tries to use a HashMap to check if any word starts with a given prefix. What is the main issue?

var map = new Dictionary();
map["apple"] = true;
map["app"] = true;

bool StartsWith(string prefix) {
    return map.ContainsKey(prefix);
}

Console.WriteLine(StartsWith("app"));
Console.WriteLine(StartsWith("apl"));

medium

A. HashMap does not support prefix search; ContainsKey checks exact keys only

B. The dictionary keys are not initialized properly

C. The StartsWith method should use map.Values instead of map.Keys

D. The code will throw a runtime exception

Solution

1. Step 1: Understand what ContainsKey does in Dictionary

   ContainsKey checks if the exact key exists, not if any key starts with the prefix.

2. Step 2: Identify why prefix search fails

   Since map only stores full words as keys, ContainsKey("app") returns true only if "app" is a full key, not if any key starts with "app".

3. Final Answer:

   HashMap does not support prefix search; ContainsKey checks exact keys only -> Option A

4. Quick Check:

   HashMap prefix search = no [OK]

Hint: ContainsKey checks exact keys, not prefixes [OK]

Common Mistakes:

• Thinking ContainsKey supports prefix matching
• Assuming dictionary keys are incomplete
• Expecting runtime errors

5. You need to implement a system that supports fast prefix queries and also stores frequency counts of words. Which approach is best and why?

hard

A. Hash Map storing only full word frequencies, no prefix support

B. Hash Map with prefix keys, but inefficient for large prefix sets

C. Trie with frequencies only at leaf nodes, no prefix counts

D. Trie with frequency counts at each node for prefix frequency queries

Solution

1. Step 1: Analyze prefix query and frequency requirements

   We want to query frequencies of prefixes, not just full words.

2. Step 2: Evaluate each approach

   A Trie with frequency counts at each node allows quick prefix frequency queries. Hash Map with full words only cannot query prefixes efficiently. Trie with frequencies only at leaves misses prefix counts. Hash Map with prefix keys is inefficient for many prefixes.

3. Final Answer:

   Trie with frequency counts at each node for prefix frequency queries -> Option D

4. Quick Check:

   Prefix frequency queries = Trie with node counts [OK]

Hint: Store counts at each Trie node for prefix frequency queries [OK]

Common Mistakes:

• Using Hash Map only for prefix queries
• Storing frequencies only at leaf nodes
• Assuming prefix keys in Hash Map scale well