Prefix Search Using Trie in DSA Java

Mental Model

A trie stores words by sharing common beginnings, so searching for words starting with a prefix is fast and easy.

Analogy: Imagine a tree where each branch is a letter, and words grow along branches. To find all words starting with a prefix, you just follow the prefix branches and look at all the leaves below.

root
 ↓
  c -> a -> t -> *
       ↓
       r -> *
  d -> o -> g -> *

* marks end of a word

Dry Run Walkthrough

Input: Insert words: cat, car, dog; Search prefix: ca

Goal: Find all words starting with prefix 'ca'

Step 1: Insert 'cat' letter by letter

root -> c -> a -> t -> *

Why: Build path for 'cat' so it can be found later

Step 2: Insert 'car' sharing prefix 'ca'

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

Why: Reuse 'ca' nodes, add 'r' branch for 'car'

Step 3: Insert 'dog' as new branch

root -> c -> a -> t -> *
               ↓
               r -> *
      ↓
      d -> o -> g -> *

Why: Add new branch for 'dog' since no common prefix with 'ca'

Step 4: Search prefix 'ca' by following nodes c -> a

At node 'a' with children t and r

Why: Find subtree where all words starting with 'ca' live

Step 5: Collect all words below 'a': 'cat' and 'car'

Words found: 'cat', 'car'

Why: These are all words starting with prefix 'ca'

Result:

Words starting with 'ca': cat, car

Annotated Code

DSA Java

import java.util.*;

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

public class PrefixSearchTrie {
    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 starting with prefix
    public List<String> searchPrefix(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 down prefix
        }
        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 (char ch : node.children.keySet()) {
            path.append(ch); // add letter
            dfs(node.children.get(ch), path, results); // recurse
            path.deleteCharAt(path.length() - 1); // backtrack
        }
    }

    public static void main(String[] args) {
        PrefixSearchTrie trie = new PrefixSearchTrie();
        trie.insert("cat");
        trie.insert("car");
        trie.insert("dog");

        List<String> words = trie.searchPrefix("ca");
        for (String w : words) {
            System.out.println(w);
        }
    }

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

create child node if missing to build path for word

curr = curr.children.get(ch);

advance current node to child to continue insertion or search

curr.isWord = true;

mark node as end of a valid word

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

stop search early if prefix path missing

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

collect all words under prefix node

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

add complete word to results when found

path.append(ch); dfs(node.children.get(ch), path, results); path.deleteCharAt(path.length() - 1);

explore each child recursively and backtrack path

Output

cat

car

Complexity Analysis

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

Space: O(n) for storing all inserted words in trie nodes

vs Alternative: Compared to scanning all words for prefix (O(n * word_length)), trie is faster for prefix search by avoiding full scans

Edge Cases

Empty prefix search

Returns all words 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; }

Insert duplicate words

Duplicates do not create extra nodes, word end marked once

DSA Java

curr.isWord = true;

When to Use This Pattern

When you need to quickly find all words starting with a prefix, use a trie to follow prefix letters and gather matches efficiently.

Common Mistakes

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

Mistake: Not backtracking the path string during DFS, causing incorrect word collection
Fix: Remove last character after recursive DFS call to restore path

Summary

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

Use when you want fast prefix-based search among many words.

The key is sharing prefix nodes so you only traverse the prefix once and then collect all matches below.

Practice

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

easy

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

B. To sort words alphabetically

C. To store numbers in sorted order

D. To perform arithmetic operations quickly

Solution

1. Step 1: Understand what prefix search means

   Prefix search means finding all words that start with a certain beginning sequence of letters.

2. Step 2: Understand Trie's role in prefix search

   A Trie stores words in a tree where each node represents a letter, making it easy to find all words sharing the same prefix by traversing the tree.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option A

4. Quick Check:

   Prefix search = efficient word lookup [OK]

Hint: Trie nodes represent letters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting data structures
• Thinking Trie is for arithmetic operations
• Assuming Trie stores numbers only

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

easy

A. class TrieNode { int[] children = new int[26]; boolean isEndOfWord; }

B. class TrieNode { char[] children = new char[26]; boolean isEndOfWord; }

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

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

Solution

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

   Each child should be a reference to another TrieNode, so the array type must be TrieNode[].

2. Step 2: Check the other parts of the class

   Boolean isEndOfWord marks if the node ends a word, which is correct in class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEndOfWord; }.

3. Final Answer:

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

4. Quick Check:

   Children are TrieNode references [OK]

Hint: Children array holds TrieNode references, not primitives [OK]

Common Mistakes:

• Using int or char arrays instead of TrieNode array
• Using String array for children
• Forgetting to mark end of word

3. Given the following code snippet, what will be the output?

Trie trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
System.out.println(trie.startsWith("ca"));
System.out.println(trie.startsWith("do"));
System.out.println(trie.startsWith("bat"));

medium

A. true
true
false

B. true
false
false

C. false
true
false

D. false
false
true

Solution

1. Step 1: Insert words into the Trie

   Words "cat", "car", and "dog" are inserted, so prefixes "ca" and "do" exist in the Trie.

2. Step 2: Check startsWith results

   startsWith("ca") returns true because "cat" and "car" start with "ca".
   startsWith("do") returns true because "dog" starts with "do".
   startsWith("bat") returns false because no word starts with "bat".

3. Final Answer:

   true true false -> Option A

4. Quick Check:

   Prefix "ca" and "do" found, "bat" not found [OK]

Hint: Check inserted words' prefixes carefully [OK]

Common Mistakes:

• Assuming startsWith returns false if word not complete
• Confusing startsWith with search for whole word
• Mixing up true/false outputs

4. The following Java method is intended to check if a prefix exists in a Trie, but it has a bug. What is the bug?

public boolean startsWith(String prefix) {
    TrieNode node = root;
    for (int i = 0; i <= prefix.length(); i++) {
        char c = prefix.charAt(i);
        if (node.children[c - 'a'] == null) return false;
        node = node.children[c - 'a'];
    }
    return true;
}

medium

A. The root node is not initialized before the loop

B. The loop condition should be < instead of <= to avoid IndexOutOfBoundsException

C. The method should return false at the end instead of true

D. The character indexing is wrong; should use c + 'a'

Solution

1. Step 1: Analyze the for-loop condition

   The loop runs from i = 0 to i <= prefix.length(), which means it tries to access prefix.charAt(prefix.length()), causing an IndexOutOfBoundsException.

2. Step 2: Correct the loop condition

   The loop should run while i < prefix.length() to access valid characters only.

3. Final Answer:

   The loop condition should be < instead of <= to avoid IndexOutOfBoundsException -> Option B

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Loop index must be less than string length [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Incorrect character arithmetic
• Returning wrong boolean at the end

5. You want to find all words in a Trie that start with the prefix "app". Which approach correctly retrieves all such words?

hard

A. Use a hash map to store all words and filter those starting with "app"

B. Search each word in the Trie individually to check if it starts with "app"

C. Traverse the Trie to the node representing 'p' in "app", then perform a depth-first search collecting all words below

D. Insert "app" as a word and then search for it

Solution

1. Step 1: Locate the prefix node in the Trie

   Traverse the Trie following letters 'a', 'p', 'p' to reach the node representing the last 'p' in "app".

2. Step 2: Collect all words below this node

   Perform a depth-first search (DFS) from this node to find all complete words that start with "app".

3. Final Answer:

   Traverse the Trie to the node representing 'p' in "app", then perform a depth-first search collecting all words below -> Option C

4. Quick Check:

   Prefix node + DFS = all matching words [OK]

Hint: Find prefix node, then DFS to collect words [OK]

Common Mistakes:

• Checking all words instead of using Trie structure
• Using hash map instead of Trie traversal
• Confusing insertion with search