Prefix Search Using Trie in DSA Java - Build from Scratch

Prefix Search Using Trie

📖 Scenario: You are building a simple search feature for a phone contacts app. When a user types some letters, the app should quickly find all contact names that start with those letters.

🎯 Goal: Build a Trie data structure to store contact names and implement a prefix search method to find all contacts starting with a given prefix.

📋 What You'll Learn

Create a TrieNode class with children and end-of-word marker

Create a Trie class with insert and prefix search methods

Insert given contact names into the Trie

Search and return all contacts starting with a given prefix

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words starting with certain letters.

💼 Career

Understanding Tries helps in building efficient search features and is a common topic in coding interviews for software engineering roles.

1

Create TrieNode class and initialize root

Create a class called TrieNode with a Map children and a boolean isEndOfWord. Then create a class called Trie with a TrieNode root initialized in its constructor.

DSA Java

// Define TrieNode class and Trie class with root initialization
// Your code here

Hint

Think of TrieNode as a box holding links to next letters and a flag if a word ends here. The Trie has a root node to start all searches.

2

Add insert method to Trie

Inside the Trie class, add a method called insert that takes a String word. Use a for loop with variable ch to iterate over each character of word. Insert each character into the Trie by creating new TrieNode if needed. Mark the last node's isEndOfWord as true.

DSA Java

import java.util.Map;
import java.util.HashMap;

class TrieNode {
    Map children = new HashMap();
    boolean isEndOfWord = false;
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Add insert method below
    // Your code here
}

Hint

Loop through each letter. If the letter is not in children, add a new node. Move current to that child. After loop, mark end of word.

3

Add prefix search method to Trie

Inside the Trie class, add a method called searchPrefix that takes a String prefix and returns a List of all words starting with that prefix. Use a helper method collectAllWords that recursively collects words from a given TrieNode. Use a for loop with variable ch to traverse the prefix nodes.

DSA Java

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class TrieNode {
    Map children = new HashMap();
    boolean isEndOfWord = false;
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current.children.putIfAbsent(ch, new TrieNode());
            current = current.children.get(ch);
        }
        current.isEndOfWord = true;
    }

    // Add searchPrefix and collectAllWords methods below
    // Your code here
}

Hint

First find the node matching the prefix. Then recursively collect all words below it by adding letters and backtracking.

4

Test prefix search and print results

Create a main method in a Solution class. Create a Trie object called trie. Insert these exact contact names: "Alice", "Alina", "Bob", "Bobby", "Bonnie". Then call searchPrefix on "Bo" and print each result on its own line using a for loop with variable name.

DSA Java

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class TrieNode {
    Map children = new HashMap();
    boolean isEndOfWord = false;
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current.children.putIfAbsent(ch, new TrieNode());
            current = current.children.get(ch);
        }
        current.isEndOfWord = true;
    }

    public List searchPrefix(String prefix) {
        List results = new ArrayList();
        TrieNode current = root;
        for (char ch : prefix.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                return results; // empty list
            }
            current = current.children.get(ch);
        }
        collectAllWords(current, new StringBuilder(prefix), results);
        return results;
    }

    private void collectAllWords(TrieNode node, StringBuilder prefix, List results) {
        if (node.isEndOfWord) {
            results.add(prefix.toString());
        }
        for (Map.Entry entry : node.children.entrySet()) {
            prefix.append(entry.getKey());
            collectAllWords(entry.getValue(), prefix, results);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }
}

// Your code here

Hint

Insert the exact names, then search prefix "Bo" and print each found name on its own line.

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