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 character child exists?

No→Prefix not found

Yes↓

Move to child node

↓

Repeat for next character

↓

All prefix chars found

↓

Collect all words from current node

↓

Return list of words with prefix

Start from the root and follow each prefix character down the trie. If all prefix 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 change	root -> c -> a -> t*
5	Insert 'car' char 'a'	root -> c -> a -> t*	a node exists, no change	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* root -> d -> null
8	Insert 'dog' char 'o'	root -> c -> a -> t* -> r* root -> d	d -> o node created	root -> c -> a -> t* -> r* root -> d -> o -> null
9	Insert 'dog' char 'g'	root -> c -> a -> t* -> r* root -> d -> o	o -> g node created (end of word)	root -> c -> a -> t* -> r* root -> d -> o -> g*
10	Search prefix 'ca' char 'c'	root -> c -> a -> t* -> r* root -> d -> o -> g*	Move to c node	At node c
11	Search prefix 'ca' char 'a'	At node c	Move to a node	At node a
12	Prefix 'ca' found, collect words	At node a	Traverse children t* and r*	Words found: 'cat', 'car'

💡 Prefix 'ca' fully matched, words collected from node 'a'.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12
Trie Nodes	root	root -> c -> a -> t*	root -> c -> a -> t* -> r*	root -> c -> a -> t* -> r* root -> d -> o -> g*	No change, at node a for prefix 'ca'
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 child does not exist?

Because if the child node for a character already exists (see steps 4 and 5), we reuse it to avoid duplicates and keep the trie compact.

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

We mark the last character node of a word with a special flag (shown as * in Visual State), as seen in steps 3, 6, and 9.

What happens if the prefix is not found during search?

The search stops immediately when a character child does not exist (not shown here), indicating no words with that prefix.

Visual Quiz - 3 Questions

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

A Node 'd' as child of root

B Node 't' as child of 'a'

C Node 'r' as child of 'a'

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 8

C Step 7

D Step 10

💡 Hint

Look for the step where the last character node 'g' is created and marked as end of word.

According to variable_tracker, what is the current node after step 12?

A root

B node a

C node c

D node t

💡 Hint

Check the 'Current Node' row in variable_tracker after step 12.

Concept Snapshot

Trie stores words as paths from root to nodes.
Insert: create nodes for chars if missing.
Mark end of word nodes.
Prefix search: follow prefix chars.
If prefix found, collect all words below.
Efficient for prefix-based queries.

Full Transcript

This visual trace shows how a trie is built by inserting words 'cat', 'car', and 'dog'. Each character is a node. If a node for a character exists, it is reused. The end of a word is marked with a special flag. Searching for prefix 'ca' involves moving from root to 'c' node, then to 'a' node. Once prefix is matched, all words below are collected. The execution table tracks each insertion and search step, showing node creation and traversal. Variable tracker shows trie structure and current node changes. Key moments clarify why nodes are created only if missing, how word ends are marked, and what happens if prefix is missing. The quiz tests understanding of node creation, word insertion, and search position. The snapshot summarizes trie usage for prefix search.

Practice

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

easy

A. To reverse strings quickly

B. To sort words alphabetically

C. To store words in a hash table

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

Solution

1. Step 1: Understand Trie usage

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

2. Step 2: Identify prefix search goal

   Prefix search means finding all words starting with a given prefix efficiently, which Trie supports well.

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 fast searches [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie is a hash table
• Assuming Trie reverses strings

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

easy

A. struct TrieNode { bool isEnd; TrieNode* children[26]; };

B. struct TrieNode { int value; TrieNode children; };

C. class TrieNode { bool isEnd; vector<int> children; };

D. struct TrieNode { bool isEnd; TrieNode children[]; };

Solution

1. Step 1: Check Trie node structure

   A Trie node typically has a boolean to mark word end and an array of pointers for children nodes.

2. Step 2: Match correct syntax

   struct TrieNode { bool isEnd; TrieNode* children[26]; }; correctly declares a boolean and an array of 26 pointers for English lowercase letters.

3. Final Answer:

   struct TrieNode { bool isEnd; TrieNode* children[26]; }; -> Option A

4. Quick Check:

   Trie node = bool + pointer array [OK]

Hint: Trie nodes have boolean + fixed-size pointer array [OK]

Common Mistakes:

• Using vector<int> instead of pointers
• Missing pointer (*) in children array
• Declaring children as single object, not array

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

Trie trie;
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
vector<string> result = trie.searchPrefix("ca");
for (auto &word : result) std::cout << word << " ";

medium

A. cat car

B. dog

C. cat dog car

D. car cat dog

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted. Trie stores them by characters.

2. Step 2: Search prefix "ca"

   Searching prefix "ca" returns all words starting with "ca", which are "cat" and "car".

3. Final Answer:

   cat car -> Option A

4. Quick Check:

   Prefix "ca" matches "cat" and "car" [OK]

Hint: Search returns words starting exactly with prefix [OK]

Common Mistakes:

• Including words without the prefix
• Assuming order is alphabetical by default
• Confusing prefix search with full word search

4. Identify the bug in this Trie insert function snippet:

void insert(string word) {
  TrieNode* node = root;
  for (char c : word) {
    int index = c - 'a';
    if (!node->children[index])
      node->children[index] = new TrieNode();
    node = node->children[index];
  }
  node->isEnd = false;
}

medium

A. Children array should be vector, not array

B. isEnd should be set to true after insertion

C. Index calculation is incorrect

D. Root node is not initialized

Solution

1. Step 1: Review isEnd assignment

   After inserting a word, the node representing last character should mark end of word by setting isEnd to true.

2. Step 2: Identify incorrect isEnd value

   Code sets isEnd to false, which is wrong and will cause search failures.

3. Final Answer:

   isEnd should be set to true after insertion -> Option B

4. Quick Check:

   Mark word end with isEnd = true [OK]

Hint: Set isEnd true at word end to mark complete word [OK]

Common Mistakes:

• Setting isEnd to false instead of true
• Forgetting to initialize root node
• Miscomputing index from character

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

hard

A. Use a hash map instead of Trie for prefix and length search

B. Search prefix "app" and return all words regardless of length

C. Search prefix "app" in Trie, then collect words with length 5 only

D. Search all words and filter those starting with "app" and length 5

Solution

1. Step 1: Perform prefix search "app" in Trie

   Traverse Trie nodes for prefix "app" to reach subtree containing all matching words.

2. Step 2: Filter collected words by length 5

   From subtree, collect only words whose length equals 5 to meet the length condition.

3. Final Answer:

   Search prefix "app" in Trie, then collect words with length 5 only -> Option C

4. Quick Check:

   Prefix search + length filter = Search prefix "app" in Trie, then collect words with length 5 only [OK]

Hint: Filter length after prefix search for efficient results [OK]

Common Mistakes:

• Returning all prefix matches without length check
• Filtering all words instead of prefix subtree
• Using hash map losing prefix search efficiency