Autocomplete System with Trie in DSA Java - Execution Trace

Concept Flow - Autocomplete System with Trie

Start: Insert words into Trie

↓

For each word:

↓

For each char in word

↓

Check if char node exists

↓

Move to next

↓

Mark end of word

↓

User types prefix

↓

Traverse Trie for prefix

↓

If prefix node found

↓

Collect all words from prefix node

↓

Return autocomplete suggestions

↓

End

Insert words character by character into the Trie, marking word ends. For autocomplete, traverse Trie by prefix, then collect all words below that node.

Execution Sample

DSA Java

Trie trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
List<String> res = trie.autocomplete("ca");

Insert words 'cat', 'car', 'dog' into Trie, then autocomplete for prefix 'ca' to get ['cat', 'car'].

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat' char 'c'	Root -> c	Create node 'c' from root	root -> c -> null
2	Insert 'cat' char 'a'	Root -> c -> a	Create node 'a' from 'c'	root -> c -> a -> null
3	Insert 'cat' char 't'	Root -> c -> a -> t	Create node 't' from 'a', mark end	root -> c -> a -> t*
4	Insert 'car' char 'c'	Root -> c -> a -> t*	Node 'c' exists, move to 'c'	root -> c -> a -> t*
5	Insert 'car' char 'a'	Root -> c -> a -> t*	Node 'a' exists, move to 'a'	root -> c -> a -> t*
6	Insert 'car' char 'r'	Root -> c -> a -> t*, r	Create node 'r' from 'a', mark end	root -> c -> a -> t*, r*
7	Insert 'dog' char 'd'	Root -> c -> a -> t*, r*; d	Create node 'd' from root	root -> c -> a -> t*, r*; d -> null
8	Insert 'dog' char 'o'	Root -> c -> a -> t*, r*; d -> o	Create node 'o' from 'd'	root -> c -> a -> t*, r*; d -> o -> null
9	Insert 'dog' char 'g'	Root -> c -> a -> t*, r*; d -> o -> g	Create node 'g' from 'o', mark end	root -> c -> a -> t*, r*; d -> o -> g*
10	Autocomplete prefix 'ca' char 'c'	Root -> c -> a -> t*, r*; d -> o -> g*	Move to node 'c'	At node 'c'
11	Autocomplete prefix 'ca' char 'a'	Root -> c -> a -> t*, r*; d -> o -> g*	Move to node 'a'	At node 'a'
12	Collect words from node 'a'	Root -> c -> a -> t*, r*; d -> o -> g*	Traverse children 't*' and 'r*'	Found words: 'cat', 'car'
13	Return autocomplete results	Root -> c -> a -> t*, r*; d -> o -> g*	Return ['cat', 'car']	Autocomplete: ['cat', 'car']

💡 Autocomplete done after collecting all words from prefix node 'a'.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	After Step 9	After Step 11	Final
Trie Nodes Count	0	1 (c)	3 (c,a,t)	4 (c,a,t,r)	7 (c,a,t,r,d,o,g)	7	7
Current Node	root	c	t	r	g	a	a
Words Collected	[]	[]	[]	[]	[]	[]	['cat', 'car']

Key Moments - 3 Insights

Why do we create new nodes only when the character node doesn't exist?

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

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 flag). For example, in step 3, 't' is marked as end for 'cat'.

Why do we traverse all children nodes after reaching the prefix node during autocomplete?

Because all words starting with the prefix are in the subtree below that node. Step 12 shows traversal of 't*' and 'r*' nodes to collect 'cat' and 'car'.

Visual Quiz - 3 Questions

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

A Create node 't' from 'a'

B Create node 'r' from 'a' and mark end of word

C Move to existing node 'r'

D Mark node 'a' 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 7

B Step 6

C Step 9

D Step 3

💡 Hint

Look for when the last character 'g' of 'dog' is created and marked as end.

If we change the prefix to 'do' in autocomplete, which node will be the last node traversed before collecting words?

A Node 'o'

B Node 'd'

C Node 'g'

D Node 'a'

💡 Hint

Refer to steps 10 and 11 where prefix characters are traversed.

Concept Snapshot

Trie stores words by characters in nodes.
Insert: create nodes for chars if missing, mark end of word.
Autocomplete: traverse prefix nodes, then collect all words below.
Shared prefixes use same nodes, saving space.
End nodes mark complete words.
Traversal for autocomplete returns all matching words.

Full Transcript

This visualization shows how an autocomplete system uses a Trie data structure. Words like 'cat', 'car', and 'dog' are inserted 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 to show the word ends there. For autocomplete, we traverse the Trie nodes matching the prefix typed by the user. Once at the prefix node, we collect all words in its subtree. The execution table tracks each insertion and traversal step, showing how nodes are created or reused, and how words are collected. The variable tracker shows the number of nodes, current node position, and collected words at each step. Key moments clarify why nodes are created only when missing, how word ends are marked, and why we traverse all children for autocomplete. The quiz tests understanding of these steps. The snapshot summarizes the Trie operations for autocomplete.

Practice

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

easy

A. To count the frequency of words

B. To efficiently store and search prefixes of words

C. To sort words alphabetically

D. To encrypt the stored words

Solution

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

   A Trie is a tree-like data structure that stores characters of words in a way that common prefixes share nodes.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires quick lookup of words starting with a given prefix, which Trie supports efficiently.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option B

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is built for prefix-based fast search [OK]

Common Mistakes:

• Confusing Trie with sorting data structure
• Thinking Trie encrypts data
• Assuming Trie counts word frequency only

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

easy

A. class TrieNode { char[] children = new char[26]; boolean isWord; }

B. class TrieNode { int[] children = new int[26]; boolean isWord; }

C. class TrieNode { String[] children = new String[26]; boolean isWord; }

D. class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isWord; }

Solution

1. Step 1: Identify the correct data type for children nodes

   Each child should be a reference to another TrieNode, so an array of TrieNode objects is needed.

2. Step 2: Check other options for correctness

   Options B, C, and D use primitive types or String arrays which cannot represent child nodes properly.

3. Final Answer:

   class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isWord; } -> Option D

4. Quick Check:

   Children = TrieNode array [OK]

Hint: Children must be TrieNode references, not primitives [OK]

Common Mistakes:

• Using int or char arrays instead of TrieNode array
• Using String array for children
• Forgetting to initialize children array

3. What will be the output of the following Java code snippet using a Trie for autocomplete?

Trie trie = new Trie();
trie.insert("dog");
trie.insert("deer");
trie.insert("deal");
List<String> results = trie.autocomplete("de");
System.out.println(results);

medium

A. ["deer", "deal"]

B. ["dog", "deer", "deal"]

C. ["dog"]

D. []

Solution

1. Step 1: Understand inserted words and prefix search

   Words inserted are "dog", "deer", and "deal". The prefix searched is "de".

2. Step 2: Filter words starting with prefix "de"

   Only "deer" and "deal" start with "de"; "dog" starts with "do".

3. Final Answer:

   ["deer", "deal"] -> Option A

4. Quick Check:

   Autocomplete("de") = ["deer", "deal"] [OK]

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

Common Mistakes:

• Including words not matching prefix
• Returning empty list by mistake
• Confusing prefix "de" with "do"

4. Identify the bug in this Trie insertion method snippet and select the fix:

public void insert(String word) {
  TrieNode node = root;
  for (int i = 0; i <= word.length(); i++) {
    char c = word.charAt(i);
    int index = c - 'a';
    if (node.children[index] == null) {
      node.children[index] = new TrieNode();
    }
    node = node.children[index];
  }
  node.isWord = true;
}

medium

A. Change loop condition to i < word.length() to avoid IndexOutOfBoundsException

B. Initialize root inside the loop

C. Remove node.isWord assignment

D. Change char c to int c

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= word.length(), which causes i to reach word.length(), an invalid index for charAt.

2. Step 2: Fix loop condition

   Changing condition to i < word.length() prevents IndexOutOfBoundsException by stopping before invalid index.

3. Final Answer:

   Change loop condition to i < word.length() to avoid IndexOutOfBoundsException -> Option A

4. Quick Check:

   Loop index < word.length() [OK]

Hint: Loop over string chars with i < length, not <= length [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring IndexOutOfBoundsException
• Misunderstanding charAt indexing

5. You want to extend a Trie-based autocomplete system to return suggestions sorted by frequency of word usage. Which data structure modification is best to support this efficiently?

hard

A. Store words in a linked list attached to each node

B. Sort all words alphabetically after each insertion

C. Store a frequency count at each word node and use a priority queue during search

D. Use a hash map to store words and frequencies separately from the Trie

Solution

1. Step 1: Understand frequency tracking in Trie nodes

   Storing frequency count at each word node allows tracking how often each word is used.

2. Step 2: Use priority queue to get top frequent words during autocomplete

   During prefix search, a priority queue can efficiently retrieve words with highest frequency.

3. Final Answer:

   Store a frequency count at each word node and use a priority queue during search -> Option C

4. Quick Check:

   Frequency + priority queue = efficient sorted suggestions [OK]

Hint: Use frequency counts + priority queue for sorted autocomplete [OK]

Common Mistakes:

• Sorting all words after each insertion (inefficient)
• Separating frequency from Trie nodes (loses prefix efficiency)
• Using linked list for sorting (slow access)