Prefix Search Using Trie in DSA C - Execution Trace

Concept Flow - Prefix Search Using Trie

Start at root node

↓

For each character in prefix

↓

Check if child node for char exists?

No→Prefix not found

Yes↓

Move to child node

↓

Repeat for next char

↓

All chars processed

↓

Prefix found, collect all words below

↓

Return list of words with prefix

Start from the root and follow each character of the prefix down the trie. If all characters exist, collect all words below that node.

Execution Sample

DSA C

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

Insert words 'cat', 'car', 'dog' into trie, then search for words starting with prefix 'ca'.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat' char 'c'	root	root -> c node created	root -> c -> null
2	Insert 'cat' char 'a'	root -> c	c -> a node created	root -> c -> a -> null
3	Insert 'cat' char 't'	root -> c -> a	a -> t node created (end of word)	root -> c -> a -> t*
4	Insert 'car' char 'c'	root -> c -> a -> t*	c node exists, no new node	root -> c -> a -> t*
5	Insert 'car' char 'a'	root -> c -> a -> t*	a node exists, no new node	root -> c -> a -> t*
6	Insert 'car' char 'r'	root -> c -> a -> t*	a -> r node created (end of word)	root -> c -> a -> t*, r*
7	Insert 'dog' char 'd'	root -> c -> a -> t*, r*	root -> d node created	root -> c -> a -> t*, r*; d -> null
8	Insert 'dog' char 'o'	root -> c -> a -> t*, r*; d	d -> o node created	root -> c -> a -> t*, r*; d -> o -> null
9	Insert 'dog' char 'g'	root -> c -> a -> t*, r*; d -> o	o -> g node created (end of word)	root -> c -> a -> t*, r*; d -> o -> g*
10	Search prefix 'ca' char 'c'	root -> c -> a -> t*, r*; d -> o -> g*	Move to c node	At node c
11	Search prefix 'ca' char 'a'	root -> c -> a -> t*, r*; d -> o -> g*	Move to a node	At node a
12	Collect words below node 'a'	root -> c -> a -> t*, r*; d -> o -> g*	Traverse children t* and r*	Words found: 'cat', 'car'

💡 All prefix characters found; collected words under last node.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12
Trie Nodes	root only	root -> c -> a -> t*	root -> c -> a -> t*, r*	root -> c -> a -> t*, r*; d -> o -> g*	root -> c -> a -> t*, r*; d -> o -> g*
Current Node	root	root	root	root	node 'a'
Words Collected	[]	[]	[]	[]	['cat', 'car']

Key Moments - 3 Insights

Why do we create new nodes only when the character path does not exist?

Because existing nodes represent shared prefixes. See steps 4 and 5 where 'c' and 'a' nodes already exist, so no new nodes are created.

How do we know when a word ends in the trie?

We mark the last character node of a word with an end-of-word marker (shown as *). For example, 't*' in step 3 means 'cat' ends there.

What happens if the prefix is not found during search?

The search stops immediately when a character node is missing. Here, all prefix chars exist, so search continues to collect words.

Visual Quiz - 3 Questions

Look at the execution table at step 6, which new node is created?

A Node 't' as child of 'a'

B Node 'r' as child of 'a'

C Node 'd' as child of root

D Node 'o' as child of 'd'

💡 Hint

Check the Pointer Changes and Visual State columns at step 6.

At which step does the trie first contain the word 'dog'?

A Step 9

B Step 7

C Step 8

D Step 10

💡 Hint

Look for the end-of-word marker (*) for 'g' in the Visual State column.

If we searched prefix 'do' instead of 'ca', at which step would the search fail or succeed?

A Fail at step 10

B Succeed at step 11

C Succeed at step 12

D Fail at step 11

💡 Hint

Check the nodes for 'd' and 'o' in the trie after insertions.

Concept Snapshot

Prefix Search Using Trie:
- Start at root node
- For each prefix char, move to child node if exists
- If any char missing, prefix not found
- If all chars found, collect all words below
- End-of-word nodes mark complete words
- Efficient for prefix-based word search

Full Transcript

This visual trace shows how prefix search works using a trie data structure. We insert words 'cat', 'car', and 'dog' step-by-step, creating nodes only when needed. Each character is a node, and end-of-word nodes are marked. Searching a prefix means following nodes for each prefix character. If all exist, we collect all words below that node. The execution table tracks each insertion and search step, showing node creation and traversal. The variable tracker shows how the trie grows and how the current node moves during search. Key moments clarify why nodes are shared, how word ends are marked, and what happens if prefix is missing. The quiz tests understanding of node creation, word insertion, and prefix search success.

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