Why Trie Exists and What Hash Map Cannot Do for Strings in DSA C - See It Work

Why Trie Exists and What Hash Map Cannot Do for Strings

📖 Scenario: Imagine you are building a phone contact list app. You want to quickly find all contacts starting with certain letters, like "Al" or "Jo". Using a hash map to store names is fast for exact matches but not for finding names by prefix. A Trie (prefix tree) helps solve this problem efficiently.

🎯 Goal: Build a simple Trie data structure in C to store a list of names. Then, show how to find all names starting with a given prefix. This will demonstrate why Trie is useful and what a hash map cannot do easily for strings.

📋 What You'll Learn

Create a Trie node structure with children for each letter

Insert given names into the Trie

Search for names by prefix using the Trie

Print all names that start with the given prefix

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words starting with certain letters.

💼 Career

Understanding Tries helps in roles involving text processing, search optimization, and building efficient data retrieval systems.

1

Create Trie Node Structure

Define a struct called TrieNode with an array of 26 TrieNode* pointers named children and an int called isEndOfWord to mark the end of a word.

DSA C

// Define the TrieNode struct with children and isEndOfWord
// Your code here

Hint

Think of each node as a box with 26 smaller boxes inside, one for each letter a-z. The isEndOfWord tells if a word ends here.

2

Create a Function to Initialize a Trie Node

Write a function called getNode that returns a pointer to a new TrieNode. Initialize all children pointers to NULL and isEndOfWord to 0.

DSA C

typedef struct TrieNode {
    struct TrieNode* children[26];
    int isEndOfWord;
} TrieNode;

// Write getNode function to create and initialize a TrieNode
// Your code here

Hint

Use malloc to create space for the node. Set all children to NULL and isEndOfWord to 0.

3

Insert Words into the Trie

Write a function called insert that takes a TrieNode* called root and a char* called key. Insert the string key into the Trie by creating nodes for each letter. Mark the last node's isEndOfWord as 1.

DSA C

typedef struct TrieNode {
    struct TrieNode* children[26];
    int isEndOfWord;
} TrieNode;

#include 

TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = 0;
    for (int i = 0; i children[i] = NULL;
    }
    return node;
}

// Insert the word key into the Trie starting from root
// Your code here

Hint

Walk through each letter of the word. If the child node for that letter is missing, create it. At the end, mark the node as end of a word.

4

Print All Words Starting with a Prefix

Write a function called printWordsWithPrefix that takes a TrieNode* called root, a char* called prefix, and prints all words in the Trie that start with prefix. Then, in main, create a Trie, insert the words "apple", "app", "bat", and "ball". Finally, print all words starting with "app".

DSA C

typedef struct TrieNode {
    struct TrieNode* children[26];
    int isEndOfWord;
} TrieNode;

#include 
#include 

TrieNode* getNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = 0;
    for (int i = 0; i children[i] = NULL;
    }
    return node;
}

void insert(TrieNode* root, char* key) {
    TrieNode* pCrawl = root;
    for (int i = 0; key[i] != '\0'; i++) {
        int index = key[i] - 'a';
        if (pCrawl->children[index] == NULL) {
            pCrawl->children[index] = getNode();
        }
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = 1;
}

// Your code here

Hint

First find the node matching the prefix. Then print all words below that node by exploring children recursively.

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