Autocomplete System with Trie in DSA C - Execution Trace

Concept Flow - Autocomplete System with Trie

Start: Insert words into Trie

↓

For each word: For each char

↓

Check if char node exists

↓

Move to next

↓

Mark end of word

↓

Autocomplete query: Traverse Trie by prefix

↓

If prefix node found

↓

DFS from prefix node to collect words

↓

Return list of autocomplete suggestions

↓

End

Insert words character by character into the Trie, creating nodes as needed. For autocomplete, traverse the Trie by prefix, then collect all words below that prefix node.

Execution Sample

DSA C

Insert("cat")
Insert("car")
Insert("dog")
Autocomplete("ca")

Insert three words into the Trie, then find all words starting with "ca".

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat' char 'c'	root -> c	root.children['c'] = new node	root -> c
2	Insert 'cat' char 'a'	root -> c -> a	c.children['a'] = new node	root -> c -> a
3	Insert 'cat' char 't'	root -> c -> a -> t	a.children['t'] = new node (end of word)	root -> c -> a -> t*
4	Insert 'car' char 'c' (exists)	root -> c -> a -> t*	move to c node	root -> c -> a -> t*
5	Insert 'car' char 'a' (exists)	root -> c -> a -> t*	move to a node	root -> c -> a -> t*
6	Insert 'car' char 'r'	root -> c -> a -> t*, r	a.children['r'] = new node (end of word)	root -> c -> a -> t*, r*
7	Insert 'dog' char 'd'	root -> c -> a -> t*, r*, d	root.children['d'] = new node	root -> c -> a -> t*, r*, d
8	Insert 'dog' char 'o'	root -> c -> a -> t*, r*, d -> o	d.children['o'] = new node	root -> c -> a -> t*, r*, d -> o
9	Insert 'dog' char 'g'	root -> c -> a -> t*, r*, d -> o -> g	o.children['g'] = new node (end of word)	root -> c -> a -> t*, r*, d -> o -> g*
10	Autocomplete 'ca' prefix traversal	root -> c -> a	move root -> c -> a	prefix node at 'a'
11	DFS collect words from 'a'	root -> c -> a -> t*, r*	collect 'cat' and 'car'	Suggestions: ['cat', 'car']

💡 All words inserted and autocomplete suggestions collected for prefix 'ca'.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 11
Trie Nodes	root	root -> c -> a -> t*	root -> c -> a -> t*, r*	root -> c -> a -> t*, r*, d -> o -> g*	Same as after Step 9
Current Pointer	root	at 't' node	at 'r' node	at 'g' node	at 'a' node (prefix for autocomplete)
Autocomplete Suggestions	[]	[]	[]	[]	['cat', 'car']

Key Moments - 3 Insights

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

Because existing nodes represent shared prefixes. See steps 4 and 5 where 'c' and 'a' nodes already exist, so we move pointers instead of creating new nodes.

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

We mark the last character node of a word as an end node (with a special flag). In steps 3, 6, and 9, nodes 't', 'r', and 'g' are marked as end of words.

How does autocomplete find all words starting with a prefix?

After reaching the prefix node (step 10), we do a depth-first search (DFS) to collect all words below it (step 11). This gathers all completions.

Visual Quiz - 3 Questions

Look at the execution table at step 6. What operation is performed?

A Create new node for 't' under 'a'

B Move pointer to existing 'r' node

C Create new node for 'r' under 'a' and mark end of word

D Mark 'a' node as end of word

💡 Hint

Check the 'Operation' and 'Pointer Changes' columns at step 6 in the execution table.

At which step does the Trie first contain the word 'dog' completely inserted?

A Step 9

B Step 7

C Step 8

D Step 10

💡 Hint

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

If we change the autocomplete prefix to 'do', what would the suggestions be?

A ['cat', 'car']

B ['dog']

C []

D ['ca', 'car', 'dog']

💡 Hint

Check the variable_tracker for suggestions collected after DFS from prefix node.

Concept Snapshot

Trie stores words by characters in a tree structure.
Insert words by creating nodes for each char if missing.
Mark end of word nodes to identify complete words.
Autocomplete: traverse prefix, then DFS to collect words.
Efficient prefix search with shared nodes saves space and time.

Full Transcript

We build a Trie by inserting words character by character. Each character is a node. If a node for a character exists, we move to it; otherwise, we create it. The last character node of a word is marked as an end node. For autocomplete, we traverse the Trie to the prefix node, then collect all words below it using depth-first search. This way, we efficiently find all words starting with the prefix. The execution table shows each insertion step and the autocomplete process, while the variable tracker shows how the Trie nodes and pointers change. Key moments clarify why nodes are created only when needed, how word ends are marked, and how autocomplete collects suggestions.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To store words in a tree structure for fast prefix search

B. To sort words alphabetically before searching

C. To store words in a linked list for sequential access

D. To compress words into a hash table for quick lookup

Solution

1. Step 1: Understand the role of Trie in autocomplete

   A Trie stores words character by character in a tree, allowing quick prefix matching.

2. Step 2: Compare with other data structures

   Linked lists and hash tables do not efficiently support prefix searches like Tries do.

3. Final Answer:

   To store words in a tree structure for fast prefix search -> Option A

4. Quick Check:

   Trie = fast prefix search [OK]

Hint: Trie = tree for prefixes, perfect for autocomplete [OK]

Common Mistakes:

• Confusing Trie with hash table
• Thinking linked list is efficient for prefix search
• Assuming sorting alone solves autocomplete

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

easy

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

B. typedef struct TrieNode { struct TrieNode* children[52]; int isEndOfWord; } TrieNode;

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

D. typedef struct TrieNode { struct TrieNode* children; int isEndOfWord; } TrieNode;

Solution

1. Step 1: Identify the size of children array for lowercase letters

   There are 26 lowercase English letters, so children array size should be 26.

2. Step 2: Check the structure correctness

   Each node has an array of pointers to children and a flag for end of word.

3. Final Answer:

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

4. Quick Check:

   26 children for lowercase letters [OK]

Hint: 26 children pointers for lowercase English letters [OK]

Common Mistakes:

• Using 52 for uppercase + lowercase without clarification
• Using 10 for digits only
• Not using array for children pointers

3. Given the following code snippet inserting words into a Trie and searching for prefix "app":

insert("apple");
insert("app");
insert("application");
searchPrefix("app");

What will searchPrefix("app") return?

medium

A. ["app"]

B. ["app", "apple", "application"]

C. ["apple", "application"]

D. []

Solution

1. Step 1: Understand insertion of words

   Words "apple", "app", and "application" are inserted, all sharing prefix "app".

2. Step 2: Search prefix "app" returns all words starting with "app"

   So, it returns all three words: "app", "apple", and "application".

3. Final Answer:

   ["app", "apple", "application"] -> Option B

4. Quick Check:

   Prefix "app" matches 3 words [OK]

Hint: Prefix search returns all words starting with prefix [OK]

Common Mistakes:

• Returning only exact matches
• Missing shorter word "app"
• Returning empty list incorrectly

4. Consider this buggy C code snippet for inserting a word into a Trie:

void insert(TrieNode* root, const 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));
      memset(node->children[index], 0, sizeof(TrieNode));
    }
    node = node->children[index];
  }
  node->isEndOfWord = 1;
}

What is the main bug in this code?

medium

A. Root node is not checked for NULL

B. Index calculation is incorrect

C. isEndOfWord is set before loop

D. New nodes are not initialized after malloc

Solution

1. Step 1: Analyze malloc usage for new nodes

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

2. Step 2: Consequence of missing initialization

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

3. Final Answer:

   New nodes are not initialized after malloc -> Option D

4. Quick Check:

   malloc needs initialization [OK]

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

Common Mistakes:

• Assuming malloc zeroes memory
• Thinking index calculation is wrong
• Ignoring initialization of isEndOfWord

5. You want to extend a Trie-based autocomplete system to support case-insensitive search for English letters (both uppercase and lowercase). Which modification is the best approach?

hard

A. Store words as-is and compare characters ignoring case during search only

B. Increase children array size to 52 to store uppercase and lowercase separately

C. Convert all input words to lowercase before insertion and search, keep children array size 26

D. Use a hash map instead of array for children to store any character

Solution

1. Step 1: Consider memory and complexity

   Using 52 children doubles memory; hash map adds overhead; ignoring case only during search is inefficient.

2. Step 2: Normalize input for simplicity

   Converting all words to lowercase before insertion and search simplifies Trie structure and ensures consistent matching.

3. Final Answer:

   Convert all input words to lowercase before insertion and search, keep children array size 26 -> Option C

4. Quick Check:

   Normalize case before Trie operations [OK]

Hint: Normalize case before insert/search for simpler Trie [OK]

Common Mistakes:

• Doubling children array size unnecessarily
• Ignoring case only during search causes mismatch
• Using hash map adds complexity and overhead