Why Trie Exists and What Hash Map Cannot Do for Strings in DSA C - Why This Pattern

Mental Model

A trie stores strings by sharing common beginnings, making prefix searches fast and memory efficient. Hash maps can't do this because they treat strings as separate keys without shared parts.

Analogy: Imagine a tree of roads where each road letter leads to the next letter in a word. If many words start the same way, they share the same roads. A hash map is like separate houses with no shared roads, so it can't quickly find all words starting with the same letters.

root
 ↓
 a -> p -> p -> l -> e -> [end]
      ↓
      r -> t -> [end]

This shows words 'apple' and 'apart' sharing 'a' and 'p' roads.

Dry Run Walkthrough

Input: words: "apple", "apart"; search prefix: "ap"

Goal: Show how trie shares prefix nodes to find all words starting with "ap" efficiently, unlike hash map

Step 1: Insert 'apple' letter by letter into trie

root -> a -> p -> p -> l -> e -> [end]

Why: We build nodes for each letter to represent the word

Step 2: Insert 'apart' sharing prefix 'a' and 'p' nodes

root -> a -> p -> p -> l -> e -> [end]
               ↓
               r -> t -> [end]

Why: Shared prefix nodes save space and link words with common start

Step 3: Search prefix 'ap' by following nodes 'a' then 'p'

root -> a -> p ↑ (at prefix end)

Why: We reach the node representing prefix 'ap' quickly

Step 4: From 'p' node, find all words below: 'apple' and 'apart'

root -> a -> p -> p -> l -> e -> [end]
               ↓
               r -> t -> [end]

Why: Trie structure allows fast prefix-based retrieval

Result:

root -> a -> p -> p -> l -> e -> [end]
               ↓
               r -> t -> [end]
Words with prefix 'ap': 'apple', 'apart'

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26

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

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

// Insert a word into 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])
            curr->children[index] = getNode();
        curr = curr->children[index];
    }
    curr->isEndOfWord = 1;
}

// Search prefix in trie, return node at prefix end or NULL
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])
            return NULL;
        curr = curr->children[index];
    }
    return curr;
}

// Recursive helper to print all words from given node
void printWords(TrieNode* node, char* buffer, int depth) {
    if (node->isEndOfWord) {
        buffer[depth] = '\0';
        printf("%s\n", buffer);
    }
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->children[i]) {
            buffer[depth] = 'a' + i;
            printWords(node->children[i], buffer, depth + 1);
        }
    }
}

int main() {
    TrieNode* root = getNode();
    const char* words[] = {"apple", "apart"};
    int n = 2;
    for (int i = 0; i < n; i++) {
        insert(root, words[i]);
    }
    const char* prefix = "ap";
    TrieNode* prefixNode = searchPrefix(root, prefix);
    if (prefixNode) {
        char buffer[100];
        strcpy(buffer, prefix);
        printf("Words with prefix '%s':\n", prefix);
        printWords(prefixNode, buffer, strlen(prefix));
    } else {
        printf("No words found with prefix '%s'\n", prefix);
    }
    return 0;
}

for (int i = 0; key[i] != '\0'; i++) {

iterate over each letter to insert nodes or reuse existing

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

create new node only if letter path does not exist

curr = curr->children[index];

move current pointer to next letter node

curr->isEndOfWord = 1;

mark end of inserted word

for (int i = 0; prefix[i] != '\0'; i++) {

traverse trie nodes to find prefix end

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

stop if prefix path missing

if (node->isEndOfWord) {

print word when end of word reached

printWords(node->children[i], buffer, depth + 1);

recursively explore all child nodes to print words

Output

Words with prefix 'ap':

apple

apart

Complexity Analysis

Time: O(m) for insert and search where m is length of word or prefix because we follow or create nodes letter by letter

Space: O(ALPHABET_SIZE * m) in worst case for new words with no shared prefix because each letter needs a node

vs Alternative: Hash map insertion/search is O(m) average but cannot share prefix nodes, so prefix search requires checking all keys, making it slower and more memory heavy for prefix queries

Edge Cases

empty string insertion

marks root as end of word, allowing empty string to be stored

DSA C

curr->isEndOfWord = 1;

search prefix not present

searchPrefix returns NULL and no words printed

DSA C

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

words with shared prefix

nodes are reused, saving space and enabling fast prefix search

DSA C

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

When to Use This Pattern

When you need to find all words starting with a prefix quickly or want to save memory by sharing common string parts, reach for the trie pattern because hash maps treat strings as separate keys without shared structure.

Common Mistakes

Mistake: Trying to use hash map for prefix search by checking all keys
Fix: Use trie to share prefix nodes and avoid scanning all keys

Mistake: Not marking end of word in trie nodes
Fix: Set isEndOfWord flag to know when a word ends

Mistake: Creating new nodes for every letter even if path exists
Fix: Check if child node exists before creating new node

Summary

Trie stores strings by sharing common prefixes for fast prefix search.

Use trie when you need efficient prefix queries or memory savings on many strings with shared starts.

The key insight is that trie nodes represent letters and shared paths let you find prefixes quickly.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing strings?

easy

A. Because Trie is faster for all types of data retrieval

B. Because Trie supports efficient prefix search which Hash Map cannot do easily

C. Because Hash Map cannot store strings as keys

D. Because Trie uses less memory than Hash Map for all data types

Solution

1. Step 1: Understand Trie and Hash Map capabilities

   Trie stores strings in a tree form allowing prefix-based queries efficiently. Hash Map stores key-value pairs but does not support prefix search efficiently.

2. Step 2: Compare prefix search ability

   Trie can quickly find all strings starting with a prefix. Hash Map requires checking all keys or extra structures, which is inefficient.

3. Final Answer:

   Because Trie supports efficient prefix search which Hash Map cannot do easily -> Option B

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Trie excels at prefix search, Hash Map does not [OK]

Common Mistakes:

• Thinking Hash Map cannot store strings as keys
• Believing Trie always uses less memory
• Assuming Trie is faster for all queries

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

easy

A. struct TrieNode { char* children; int isEndOfWord; };

B. struct TrieNode { int children; bool isEndOfWord; };

C. struct TrieNode { struct TrieNode* children[26]; bool isEndOfWord; };

D. struct TrieNode { struct TrieNode children; bool isEndOfWord; };

Solution

1. Step 1: Understand Trie node structure

   A Trie node typically has an array of pointers to child nodes (for each alphabet letter) and a boolean to mark end of word.

2. Step 2: Check each option

   struct TrieNode { struct TrieNode* children[26]; bool isEndOfWord; }; correctly declares an array of 26 pointers and a boolean flag. Others have wrong types or missing pointers.

3. Final Answer:

   struct TrieNode { struct TrieNode* children[26]; bool isEndOfWord; }; -> Option C

4. Quick Check:

   Trie node = array of pointers + bool [OK]

Hint: Trie node has pointer array for children and bool flag [OK]

Common Mistakes:

• Using int instead of pointer array for children
• Declaring children as single struct instead of array
• Confusing data types for isEndOfWord

3. What is the output of the following C code snippet that inserts "cat" and "car" into a Trie and checks prefix "ca"?

insert("cat");
insert("car");
bool result = startsWith("ca");
printf("%d", result);

medium

A. 1

B. 0

C. Compilation error

D. Undefined behavior

Solution

1. Step 1: Understand insert and startsWith functions

   Inserting "cat" and "car" adds nodes for 'c', 'a', 't' and 'r'. startsWith("ca") checks if any word starts with "ca".

2. Step 2: Check if prefix "ca" exists

   Both words start with "ca", so startsWith("ca") returns true (1).

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Prefix "ca" found = 1 [OK]

Hint: If words share prefix, startsWith returns 1 [OK]

Common Mistakes:

• Assuming startsWith returns 0 if prefix is partial
• Confusing insert with search function
• Ignoring that both words share prefix

4. Given this buggy Trie insertion code in C, what is the main error?

void insert(struct TrieNode* root, char* word) {
  struct TrieNode* node = root;
  for (int i = 0; word[i] != '\0'; i++) {
    int index = word[i] - 'a';
    if (node->children[index] == NULL) {
      node->children[index] = malloc(sizeof(struct TrieNode));
    }
    node = node->children[index];
  }
  node->isEndOfWord = true;
}

medium

A. isEndOfWord is set before loop

B. Index calculation is incorrect

C. Root node is not passed correctly

D. New nodes are not initialized to NULL

Solution

1. Step 1: Analyze node allocation

   When malloc allocates new TrieNode, its children pointers and isEndOfWord are uninitialized garbage values.

2. Step 2: Identify missing initialization

   New nodes must have children array set to NULL and isEndOfWord set to false to avoid errors during traversal.

3. Final Answer:

   New nodes are not initialized to NULL -> Option D

4. Quick Check:

   Uninitialized nodes cause bugs [OK]

Hint: Always initialize new Trie nodes after malloc [OK]

Common Mistakes:

• Thinking index calculation is wrong
• Setting isEndOfWord too early
• Assuming root node passing is incorrect

5. You want to store a large dictionary of words and quickly find all words starting with a given prefix. Why is Trie a better choice than Hash Map, and what is a key limitation of Hash Map in this scenario?

hard

A. Trie allows prefix search in O(k) time; Hash Map cannot do prefix search efficiently

B. Trie uses less memory; Hash Map cannot store strings as keys

C. Hash Map is slower for exact matches; Trie cannot store full words

D. Hash Map requires sorting keys; Trie automatically sorts keys

Solution

1. Step 1: Understand prefix search complexity

   Trie can find all words with a prefix in time proportional to prefix length (O(k)), independent of dictionary size.

2. Step 2: Identify Hash Map limitation

   Hash Map supports exact key lookup efficiently but cannot efficiently find keys by prefix without scanning all keys.

3. Final Answer:

   Trie allows prefix search in O(k) time; Hash Map cannot do prefix search efficiently -> Option A

4. Quick Check:

   Prefix search = Trie advantage [OK]

Hint: Trie = fast prefix search; Hash Map = exact match only [OK]

Common Mistakes:

• Believing Hash Map cannot store strings as keys
• Thinking Trie uses less memory always
• Confusing sorting with prefix search