Prefix Search Using Trie in DSA C

Mental Model

A trie stores words by sharing common starting letters, making it easy to find all words that start with a given prefix quickly.

Analogy: Imagine a tree where each branch is a letter, and words grow along branches. To find all words starting with 'app', you just follow the branches for 'a', then 'p', then 'p' and see all words hanging from there.

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

Each arrow is a letter link, and [end] marks a complete word.

Dry Run Walkthrough

Input: Insert words: "apple", "app", "apply"; Search prefix: "app"

Goal: Find all words in the trie that start with the prefix "app"

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

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

Why: Build the path for the word 'apple' so it can be found later

Step 2: Insert 'app' letter by letter, sharing existing nodes

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

Why: Mark 'app' as a complete word at the 'p' node without duplicating letters

Step 3: Insert 'apply' letter by letter, sharing prefix nodes

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

Why: Add 'apply' branching from 'l' node, sharing prefix with 'apple'

Step 4: Search prefix 'app' by following nodes a -> p -> p

At node 'p' marked [end], subtree includes 'l -> e [end]' and 'l -> y [end]'

Why: Find the node representing prefix 'app' to collect all words starting with it

Step 5: Collect all words from subtree under 'app' node

Words found: 'app', 'apple', 'apply'

Why: Gather all words that start with the prefix 'app'

Result:

Words starting with 'app': app -> apple -> apply

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* word) {
    TrieNode* curr = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (curr->children[index] == NULL) {
            curr->children[index] = getNode();
        }
        curr = curr->children[index]; // advance curr to next node
    }
    curr->isEndOfWord = true; // mark end of word
}

// Recursive helper to print all words from given node
void printWordsFromNode(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] != NULL) {
            prefix[length] = 'a' + i;
            printWordsFromNode(node->children[i], prefix, length + 1); // recurse deeper
        }
    }
}

// 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]; // advance curr
    }
    return curr; // node representing prefix
}

int main() {
    TrieNode* root = getNode();
    insert(root, "apple");
    insert(root, "app");
    insert(root, "apply");

    const char* prefix = "app";
    TrieNode* prefixNode = searchPrefix(root, prefix);

    if (prefixNode == NULL) {
        printf("No words found with prefix '%s'\n", prefix);
    } else {
        char buffer[100];
        strcpy(buffer, prefix);
        printWordsFromNode(prefixNode, buffer, strlen(prefix));
    }

    return 0;
}

curr = curr->children[index]; // advance curr to next node

advance curr pointer to next letter node to build or search word

curr->isEndOfWord = true; // mark end of word

mark current node as end of a complete word

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

print word when end of word node is reached during traversal

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

stop search if prefix letter path does not exist

printWordsFromNode(prefixNode, buffer, strlen(prefix));

start collecting and printing all words under prefix node

Output

app

apple

apply

Complexity Analysis

Time: O(m + n) where m is length of prefix and n is total letters in subtree under prefix node, because we traverse prefix then all matching words

Space: O(m) for prefix buffer plus O(n) recursion stack in worst case when printing all words

vs Alternative: Compared to scanning all words linearly (O(total words * average length)), trie prefix search is faster by avoiding unrelated words

Edge Cases

Empty trie (no words inserted)

Prefix search returns no words found

DSA C

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

Prefix not present in trie

Search returns NULL and prints no words found message

DSA C

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

Prefix is a complete word itself

That word is printed along with any longer words sharing the prefix

DSA C

if (node->isEndOfWord) { printf(...) }

When to Use This Pattern

When you need to quickly find all words starting with a given prefix, use a trie prefix search because it shares common prefixes and avoids scanning all words.

Common Mistakes

Mistake: Not marking the end of word node, so prefix search misses complete words
Fix: Set isEndOfWord = true at the last node of inserted words

Mistake: Not checking if child node exists before moving, causing null pointer errors
Fix: Always check if curr->children[index] is NULL before advancing

Summary

Stores words in a tree structure to find all words starting with a prefix efficiently.

Use when you want to find or autocomplete words by their starting letters quickly.

The key is to follow shared letter paths and then explore all words below the prefix node.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To perform arithmetic operations quickly

B. To sort words alphabetically

C. To store numbers in sorted order

D. To efficiently find all words that start with a given prefix

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie stores characters of words in a tree structure, allowing quick prefix lookups.

2. Step 2: Identify the main use case

   It helps find all words starting with a prefix efficiently, unlike sorting or arithmetic.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option D

4. Quick Check:

   Trie = Prefix search efficiency [OK]

Hint: Trie is built for prefix-based word retrieval [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie is for arithmetic
• Assuming Trie stores numbers only

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

easy

A. typedef struct TrieNode { int data; struct TrieNode* next; } TrieNode;

B. typedef struct TrieNode { char* word; struct TrieNode* child; } TrieNode;

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

D. typedef struct TrieNode { int value; struct TrieNode* left; struct TrieNode* right; } TrieNode;

Solution

1. Step 1: Identify Trie node components

   A Trie node has an array of pointers for each alphabet letter and a flag for word end.

2. Step 2: Match with given options

   typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode; matches this structure with 26 children pointers and an end-of-word flag.

3. Final Answer:

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

4. Quick Check:

   Trie node = children array + end flag [OK]

Hint: Trie nodes have 26 children pointers for letters a-z [OK]

Common Mistakes:

• Using linked list pointers instead of array for children
• Confusing Trie node with linked list or binary tree node
• Missing end-of-word flag

3. Given the following code snippet inserting words "cat", "car", and "dog" into a Trie, what will be the output of searching prefix "ca"?

insert("cat");
insert("car");
insert("dog");
searchPrefix("ca");

medium

A. ["cat", "car"]

B. ["dog"]

C. ["cat"]

D. []

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted, building branches for 'c' and 'd'.

2. Step 2: Search prefix "ca"

   Both "cat" and "car" start with "ca", so they are returned by searchPrefix.

3. Final Answer:

   ["cat", "car"] -> Option A

4. Quick Check:

   Prefix "ca" matches cat and car [OK]

Hint: Words starting with prefix are returned [OK]

Common Mistakes:

• Returning only one matching word
• Returning words not matching prefix
• Empty result for existing prefix

4. Consider this buggy C code snippet for inserting a word into a Trie. What is the main error?

void insert(TrieNode* root, char* word) {
  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(TrieNode));
    }
    node = node->children[index];
  }
  node->isEndOfWord = 1;
}

medium

A. New nodes are not initialized after malloc

B. Index calculation is incorrect

C. Loop condition should be i < strlen(word)

D. isEndOfWord flag is set too early

Solution

1. Step 1: Analyze node creation

   malloc allocates memory but does not initialize children pointers or isEndOfWord flag.

2. Step 2: Identify impact

   Uninitialized children pointers can cause undefined behavior during traversal or insertion.

3. Final Answer:

   New nodes are not initialized after malloc -> Option A

4. Quick Check:

   malloc needs initialization [OK]

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

Common Mistakes:

• Assuming malloc zeroes memory
• Ignoring initialization of isEndOfWord
• Misunderstanding loop condition

5. You want to find all words in a Trie that start with prefix "app" and have length exactly 5. Which approach correctly combines prefix search and length filtering?

hard

A. Collect all words in Trie, then filter those starting with "app" and length 5

B. Traverse Trie to node for "app", then collect words of length 5 from there

C. Search for "app" as a full word, then check length 5

D. Use binary search on sorted word list for prefix "app" and length 5

Solution

1. Step 1: Use Trie prefix traversal

   Traverse the Trie to the node representing the prefix "app" to limit search space.

2. Step 2: Collect words of length 5 from that node

   From this node, recursively collect words that complete to length 5.

3. Final Answer:

   Traverse Trie to node for "app", then collect words of length 5 from there -> Option B

4. Quick Check:

   Prefix traversal + length filter = Traverse Trie to node for "app", then collect words of length 5 from there [OK]

Hint: Start at prefix node, then filter by length [OK]

Common Mistakes:

• Filtering all words instead of prefix subtree
• Searching prefix as full word
• Using binary search on Trie data