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

Mental Model

A trie stores words by their letters in a tree, letting you find all words with a prefix fast. A hash map stores whole words as keys, so prefix search needs checking many keys.

Analogy: Imagine a phone book organized by first letter, then second letter, and so on (trie), versus a list of names where you look up exact names only (hash map). Finding all names starting with 'Jo' is easier in the phone book.

Trie:
root
 ↓
 j -> o -> h -> n -> null
       ↓
       o -> e -> null

Hash Map:
{ "john": val, "joe": val, "jane": val }
(no structure for prefixes)

Dry Run Walkthrough

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

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

Step 1: Insert "john" into trie letter by letter

root -> j -> o -> h -> n -> [end]
Hash Map: { "john": val }

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

Step 2: Insert "joe" into trie sharing prefix nodes

root -> j -> o -> h -> n -> [end]
           ↓
           e -> [end]
Hash Map: { "john": val, "joe": val }

Why: Reuse existing prefix nodes for 'jo' to save space

Step 3: Insert "jane" into trie diverging at second letter

root -> j -> o -> h -> n -> [end]
     ↓
     a -> n -> e -> [end]
Hash Map: { "john": val, "joe": val, "jane": val }

Why: Create new branch for different prefix 'ja'

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

At node 'o' with children h and e
Hash Map: keys checked for prefix

Why: Find node representing prefix to collect all words below

Step 5: Collect all words under 'o' node: "john", "joe"

Result: ["john", "joe"]
Hash Map: Need to check all keys for prefix

Why: Trie allows direct traversal to prefix subtree

Step 6: Hash map prefix search checks each key for prefix "jo"

Check "john" (match), "joe" (match), "jane" (no match)
Result: ["john", "joe"]

Why: Hash map lacks prefix structure, so must scan keys

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define ALPHABET_SIZE 26

// Trie node structure
typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;
} TrieNode;

// Create a new trie node
TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++)
        node->children[i] = NULL;
    return node;
}

// Insert a word into the trie
void insert(TrieNode* root, const char* key) {
    TrieNode* curr = root;
    for (int i = 0; key[i] != '\0'; i++) {
        int index = key[i] - 'a';
        if (curr->children[index] == NULL)
            curr->children[index] = getNode(); // create node if missing
        curr = curr->children[index]; // move to child
    }
    curr->isEndOfWord = true; // mark end of word
}

// Recursive helper to collect all words under a trie node
void collectWords(TrieNode* node, char* prefix, int length) {
    if (node->isEndOfWord) {
        prefix[length] = '\0';
        printf("%s\n", prefix); // print found word
    }
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->children[i]) {
            prefix[length] = 'a' + i;
            collectWords(node->children[i], prefix, length + 1); // recurse
        }
    }
}

// Search for prefix node in trie
TrieNode* searchPrefix(TrieNode* root, const char* prefix) {
    TrieNode* curr = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';
        if (curr->children[index] == NULL)
            return NULL; // prefix not found
        curr = curr->children[index];
    }
    return curr; // node at end of prefix
}

// Hash map simulation: simple array of strings
#define MAX_WORDS 10

bool startsWith(const char* word, const char* prefix) {
    for (int i = 0; prefix[i] != '\0'; i++) {
        if (word[i] != prefix[i])
            return false;
    }
    return true;
}

int main() {
    const char* words[] = {"john", "joe", "jane"};
    int n = 3;
    const char* prefix = "jo";

    // Build trie
    TrieNode* root = getNode();
    for (int i = 0; i < n; i++) {
        insert(root, words[i]);
    }

    printf("Words with prefix '%s' using Trie:\n", prefix);
    TrieNode* prefixNode = searchPrefix(root, prefix);
    if (prefixNode) {
        char buffer[50];
        strcpy(buffer, prefix);
        collectWords(prefixNode, buffer, strlen(prefix));
    } else {
        printf("No words found with prefix '%s'\n", prefix);
    }

    // Hash map prefix search simulation
    printf("\nWords with prefix '%s' using Hash Map:\n", prefix);
    for (int i = 0; i < n; i++) {
        if (startsWith(words[i], prefix)) {
            printf("%s\n", words[i]);
        }
    }

    return 0;
}

if (curr->children[index] == NULL) curr->children[index] = getNode();

create new trie node if missing to build prefix path

curr = curr->children[index];

advance current node to child to continue insertion

curr->isEndOfWord = true;

mark node as end of a valid word

for (int i = 0; prefix[i] != '\0'; i++) { int index = prefix[i] - 'a'; if (curr->children[index] == NULL) return NULL; curr = curr->children[index]; }

traverse trie nodes to find node matching prefix

if (node->isEndOfWord) { prefix[length] = '\0'; printf("%s\n", prefix); }

print word when end of word node reached during collection

for (int i = 0; i < ALPHABET_SIZE; i++) { if (node->children[i]) { prefix[length] = 'a' + i; collectWords(node->children[i], prefix, length + 1); } }

recursively explore all child nodes to collect words

for (int i = 0; i < n; i++) { if (startsWith(words[i], prefix)) { printf("%s\n", words[i]); } }

scan all keys in hash map to find those starting with prefix

Output

Words with prefix 'jo' using Trie:

john

joe



Words with prefix 'jo' using Hash Map:

john

joe

Complexity Analysis

Time: O(m + k) for trie where m is prefix length and k is number of matched words because we traverse prefix nodes then collect words; O(n * p) for hash map where n is number of words and p is prefix length because we check each word's prefix

Space: O(total letters in all words) for trie due to nodes per letter; O(n) for hash map storing all words

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

Edge Cases

Empty prefix string

Trie returns all words; hash map returns all words by scanning all keys

DSA C

if (prefixNode == NULL) return NULL;

Prefix not present in any word

Trie search returns NULL and prints no words; hash map finds no matches

DSA C

if (curr->children[index] == NULL) return NULL;

Words with shared prefixes

Trie shares nodes for common prefixes saving space; hash map stores full words separately

DSA C

if (curr->children[index] == NULL) curr->children[index] = getNode();

When to Use This Pattern

When a problem asks for fast prefix searches or autocomplete, think of using a trie because it organizes words by letters allowing quick prefix traversal.

Common Mistakes

Mistake: Trying to use a hash map for prefix search without scanning all keys
Fix: Use a trie or scan all keys in the hash map explicitly for prefix matching

Mistake: Not marking end of word in trie nodes
Fix: Set isEndOfWord true at the last letter node to identify complete words

Summary

Trie stores words letter by letter enabling fast prefix searches.

Use trie when you need efficient prefix matching or autocomplete.

The key insight is that trie nodes represent prefixes shared by multiple words, avoiding repeated scanning.

Practice

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

easy

A. Trie, because it stores characters in a tree structure allowing fast prefix search

B. Hash Map, because it stores keys with direct access for any substring

C. Array, because it stores elements sequentially for quick prefix lookup

D. Stack, because it allows last-in-first-out access which helps prefix matching

Solution

1. Step 1: Understand prefix matching requirement

   Prefix matching means finding all strings starting with a given prefix quickly.

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

   Trie stores characters in nodes along paths, enabling fast prefix traversal. Hash Map is good for exact key lookup but not efficient for prefix search.

3. Final Answer:

   Trie, because it stores characters in a tree structure allowing fast prefix search -> Option A

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Trie is best for prefix search, Hash Map for exact keys [OK]

Common Mistakes:

• Thinking Hash Map supports prefix search efficiently
• Confusing array or stack with prefix matching
• Assuming Hash Map stores substrings as keys

2. Which of the following is the correct way to insert a word into a Trie node in C?

easy

A. node->children[word[i] - 'a'] = createNode();

B. node[word[i]] = createNode();

C. node->children[word[i]] = createNode();

D. node.children[word[i] - 'a'] = createNode();

Solution

1. Step 1: Understand Trie node children indexing

   Children array is indexed by character offset from 'a', so use word[i] - 'a'.

2. Step 2: Use correct pointer syntax in C

   Since node is a pointer, use '->' to access children array.

3. Final Answer:

   node->children[word[i] - 'a'] = createNode(); -> Option A

4. Quick Check:

   Pointer access + char offset = node->children[word[i] - 'a'] = createNode(); [OK]

Hint: Use '->' for pointer and subtract 'a' for index [OK]

Common Mistakes:

• Using dot instead of arrow for pointer
• Not subtracting 'a' from character
• Using character directly as index

3. Given the following C code snippet for prefix search using a Trie, what will be the output?

TrieNode* root = createNode();
insert(root, "apple");
insert(root, "app");
insert(root, "bat");

printf("%d", startsWith(root, "app"));
printf("%d", startsWith(root, "bat"));
printf("%d", startsWith(root, "cat"));

Assume startsWith returns 1 if prefix exists, else 0.

medium

A. 111

B. 110

C. 101

D. 100

Solution

1. Step 1: Analyze inserted words and prefixes

   Words inserted: "apple", "app", "bat". Prefixes checked: "app", "bat", "cat".

2. Step 2: Check prefix existence

   "app" is prefix of "apple" and "app" -> returns 1. "bat" is inserted word -> returns 1. "cat" not inserted -> returns 0.

3. Final Answer:

   110 -> Option B

4. Quick Check:

   Prefix found = 1,1,0 [OK]

Hint: Check if prefix matches any inserted word start [OK]

Common Mistakes:

• Assuming startsWith returns count instead of boolean
• Confusing prefix with exact match
• Ignoring that 'cat' was not inserted

4. The following C code attempts to check if a prefix exists in a Trie but always returns 0. What is the bug?

int startsWith(TrieNode* root, char* prefix) {
    TrieNode* node = root;
    for (int i = 0; prefix[i]; i++) {
        if (node->children[prefix[i]] == NULL) {
            return 0;
        }
        node = node->children[prefix[i]];
    }
    return 1;
}

medium

A. Returning 1 instead of 0 when prefix is empty

B. Not checking if root is NULL before loop

C. Indexing children array without subtracting 'a' from prefix[i]

D. Using prefix[i] instead of prefix[i] - 'a' in loop condition

Solution

1. Step 1: Identify children array indexing

   Children array is indexed by character offset from 'a', so must use prefix[i] - 'a'.

2. Step 2: Explain impact of wrong indexing

   Using prefix[i] directly accesses out-of-bound indices, causing NULL always and returning 0.

3. Final Answer:

   Indexing children array without subtracting 'a' from prefix[i] -> Option C

4. Quick Check:

   Correct indexing = prefix[i] - 'a' [OK]

Hint: Always subtract 'a' when indexing children array [OK]

Common Mistakes:

• Forgetting to subtract 'a' from character
• Not checking for NULL root
• Confusing loop condition with indexing

5. You want to implement a prefix search system for millions of English words. Which approach is better and why?

1. Use a Trie to store all words and traverse nodes for prefix queries.
2. Use a Hash Map storing all prefixes as keys with lists of words as values.

Choose the best option.

hard

A. Hash Map, because it uses less memory than Trie

B. Hash Map, because it stores all prefixes explicitly for instant lookup

C. Trie, because it requires storing all prefixes as keys explicitly

D. Trie, because it uses less memory and supports fast prefix traversal

Solution

1. Step 1: Compare memory usage of Trie vs Hash Map for prefixes

   Trie stores characters in shared nodes, avoiding duplicate prefix storage. Hash Map stores every prefix explicitly, causing large memory use.

2. Step 2: Compare prefix query speed and scalability

   Trie allows fast traversal by characters without storing all prefixes. Hash Map lookup is fast but building and storing all prefixes is expensive and slow.

3. Final Answer:

   Trie, because it uses less memory and supports fast prefix traversal -> Option D

4. Quick Check:

   Memory efficient prefix search = Trie [OK]

Hint: Trie shares prefix nodes, Hash Map stores all prefixes explicitly [OK]

Common Mistakes:

• Assuming Hash Map uses less memory for prefixes
• Thinking Trie stores all prefixes as separate keys
• Ignoring scalability for millions of words