Autocomplete System with Trie in DSA Java

Mental Model

A trie stores words by sharing common prefixes, letting us quickly find all words starting with a given prefix.

Analogy: Imagine a tree of roads where each road sign is a letter. To find all shops starting with 'ca', you follow the roads 'c' then 'a' and see all shops branching from there.

root
 ↓
 c -> a -> t -> null
       ↓
       r -> null

Dry Run Walkthrough

Input: words: ["cat", "car", "cart"], prefix: "ca"

Goal: Find all words starting with prefix "ca"

Step 1: Insert "cat" into trie

root -> c -> a -> t -> null

Why: Add each letter as a node to build the word path

Step 2: Insert "car" into trie

root -> c -> a -> t -> null
               ↓
               r -> null

Why: Share prefix 'ca', add new branch for 'r'

Step 3: Insert "cart" into trie

root -> c -> a -> t -> null
               ↓
               r -> t -> null

Why: Extend 'car' branch with 't' to form 'cart'

Step 4: Search prefix "ca" in trie

At node 'a' after root -> c -> a

Why: Locate node where prefix ends to find all words below

Step 5: Collect all words from node 'a'

Found words: "cat", "car", "cart"

Why: Traverse all branches below prefix node to list completions

Result:

root -> c -> a -> t -> null
               ↓
               r -> t -> null
Words with prefix 'ca': ["cat", "car", "cart"]

Annotated Code

DSA Java

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isWord = false;
}

class AutocompleteSystem {
    private final TrieNode root = new TrieNode();

    // Insert a word into the trie
    public void insert(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            curr.children.putIfAbsent(ch, new TrieNode()); // create node if missing
            curr = curr.children.get(ch); // move to next node
        }
        curr.isWord = true; // mark end of word
    }

    // Search all words with given prefix
    public List<String> autocomplete(String prefix) {
        List<String> results = new ArrayList<>();
        TrieNode curr = root;
        for (char ch : prefix.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                return results; // prefix not found
            }
            curr = curr.children.get(ch); // move to prefix end
        }
        dfs(curr, new StringBuilder(prefix), results); // collect words
        return results;
    }

    // Depth-first search to collect words
    private void dfs(TrieNode node, StringBuilder path, List<String> results) {
        if (node.isWord) {
            results.add(path.toString()); // found a word
        }
        for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
            path.append(entry.getKey()); // add letter
            dfs(entry.getValue(), path, results); // recurse
            path.deleteCharAt(path.length() - 1); // backtrack
        }
    }

    public static void main(String[] args) {
        AutocompleteSystem ac = new AutocompleteSystem();
        String[] words = {"cat", "car", "cart"};
        for (String w : words) {
            ac.insert(w);
        }
        List<String> completions = ac.autocomplete("ca");
        System.out.println(completions);
    }
}

curr.children.putIfAbsent(ch, new TrieNode());

create child node if missing to build word path

curr = curr.children.get(ch);

advance current node to next letter node

curr.isWord = true;

mark node as end of a valid word

if (!curr.children.containsKey(ch)) { return results; }

stop search if prefix letter missing

dfs(curr, new StringBuilder(prefix), results);

start collecting all words below prefix node

if (node.isWord) { results.add(path.toString()); }

add complete word to results when end node reached

path.append(entry.getKey()); dfs(entry.getValue(), path, results); path.deleteCharAt(path.length() - 1);

explore each child node recursively and backtrack

Output

[cat, car, cart]

Complexity Analysis

Time: O(m + k) where m is prefix length and k is total letters in matched words because we traverse prefix then collect all completions

Space: O(n) for trie storage where n is total letters in all inserted words

vs Alternative: Compared to scanning all words for prefix (O(n * m)), trie reduces prefix search to O(m) plus output size

Edge Cases

Empty prefix

Returns all words stored in trie

DSA Java

for (char ch : prefix.toCharArray()) { if (!curr.children.containsKey(ch)) { return results; } curr = curr.children.get(ch); }

Prefix not in trie

Returns empty list immediately

DSA Java

if (!curr.children.containsKey(ch)) { return results; }

Words with shared prefixes

All words branching from prefix node are collected

DSA Java

dfs(curr, new StringBuilder(prefix), results);

When to Use This Pattern

When you need to quickly find all words starting with a prefix, use a trie to share prefixes and speed up search.

Common Mistakes

Mistake: Not marking the end of a word, so autocomplete returns incomplete results
Fix: Set isWord = true at the last node of each inserted word

Mistake: Not backtracking the path string during DFS, causing wrong words collected
Fix: Remove last character after recursive DFS call to restore path

Summary

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

Use when implementing autocomplete or prefix search features.

The key is sharing common prefixes so you only traverse the prefix once to find all matches.

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)