Trie Search Operation in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Searching a Word in Trie

What is the output of the following Java code that inserts words into a Trie and searches for a specific word?

DSA Java

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

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");
        System.out.println(trie.search("app"));
    }
}

A Compilation error

B false

C Runtime exception

D true

💡 Hint

Think about whether the word 'app' was inserted and if the search checks for complete words.

The word 'app' was inserted into the Trie, so searching for 'app' returns true because the node for 'p' marks the end of a word.

❓ Predict Output

intermediate

Search Result for Non-Inserted Word

What will be the output when searching for a word that was not inserted into the Trie?

DSA Java

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

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");
        System.out.println(trie.search("apples"));
    }
}

A true

B Compilation error

C false

D Runtime exception

💡 Hint

Check if the word 'apples' was inserted or if the Trie contains nodes for all its letters.

The word 'apples' was not inserted, so the search returns false because the Trie does not have a node for 's' after 'apple'.

🔧 Debug

advanced

Identify the Bug in Trie Search Method

What error will occur when running this Trie search method code?

DSA Java

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

class Trie {
    TrieNode root = new TrieNode();

    boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }
}

A StringIndexOutOfBoundsException

B NullPointerException

C Compilation error

D No error, returns correct result

💡 Hint

Check the loop boundary condition in the for loop.

The loop runs from i = 0 to i <= word.length(), which causes an index out of bounds when accessing word.charAt(i) at i == word.length().

🧠 Conceptual

advanced

Understanding Trie Search Behavior

If a Trie contains the words "cat" and "cater", what will the search method return when searching for "cate"?

A true

B false

C Compilation error

D Runtime exception

💡 Hint

Consider if "cate" is marked as a complete word in the Trie.

The search method returns false because "cate" is a prefix but not a complete word inserted in the Trie.

🚀 Application

expert

Result of Searching After Multiple Insertions

After inserting the words "dog", "door", "dorm", and "dot" into a Trie, what will be the output of searching for "dor"?

A false

B Runtime exception

C Compilation error

D true

💡 Hint

Check if "dor" was inserted or marked as a complete word.

The search returns false because "dor" is a prefix but not a complete word in the Trie.

Practice

1. What does the search operation in a Trie data structure do?

easy

A. Deletes a word from the Trie

B. Checks if a given word exists in the Trie

C. Inserts a new word into the Trie

D. Counts the total words stored in the Trie

Solution

1. Step 1: Understand the purpose of search in Trie

   The search operation is designed to check if a specific word is present in the Trie data structure.

2. Step 2: Differentiate from other operations

   Insertion adds words, deletion removes words, and counting totals words, but search only checks existence.

3. Final Answer:

   Checks if a given word exists in the Trie -> Option B

4. Quick Check:

   Search = Check word presence [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert operation
• Thinking search deletes words
• Assuming search counts words

2. Which of the following is the correct method signature for a search operation in a Trie class in Java?

easy

A. public boolean search(String word)

B. public void search(String word)

C. public int search(String word)

D. public String search(String word)

Solution

1. Step 1: Identify return type for search

   Search returns true or false depending on whether the word exists, so return type must be boolean.

2. Step 2: Check method parameters and return type

   Method takes a String word and returns boolean, so signature is public boolean search(String word).

3. Final Answer:

   public boolean search(String word) -> Option A

4. Quick Check:

   Search returns boolean [OK]

Hint: Search returns true/false, so boolean return type [OK]

Common Mistakes:

• Using void return type for search
• Returning int or String instead of boolean
• Incorrect method parameters

3. What will be the output of the following code snippet?

Trie trie = new Trie();
trie.insert("cat");
trie.insert("car");
System.out.println(trie.search("cat"));
System.out.println(trie.search("cap"));

medium

A. true
false

B. false
true

C. true
true

D. false
false

Solution

1. Step 1: Insert words "cat" and "car" into Trie

   Both words are stored in the Trie nodes.

2. Step 2: Search for "cat" and "cap"

   "cat" exists, so search returns true; "cap" does not exist, so search returns false.

3. Final Answer:

   true false -> Option A

4. Quick Check:

   Search("cat")=true, Search("cap")=false [OK]

Hint: Inserted words return true, missing words return false [OK]

Common Mistakes:

• Assuming partial matches return true
• Confusing inserted words with similar words
• Expecting search to insert missing words

4. Identify the error in the following Trie search method and select the correct fix:

public boolean search(String word) {
    TrieNode current = root;
    for (int i = 0; i <= word.length(); i++) {
        char ch = word.charAt(i);
        if (!current.children.containsKey(ch)) {
            return false;
        }
        current = current.children.get(ch);
    }
    return current.isEndOfWord;
}

medium

A. Return true immediately after first character check

B. Add null check for current before accessing children

C. Use '==' instead of 'containsKey' to check children

D. Change loop condition to i < word.length()

Solution

1. Step 1: Analyze loop boundary

   The loop uses i <= word.length(), which causes index out of bounds error when i equals word.length().

2. Step 2: Correct loop condition

   Change to i < word.length() to iterate valid indices only.

3. Final Answer:

   Change loop condition to i < word.length() -> Option D

4. Quick Check:

   Loop index must be less than length [OK]

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

Common Mistakes:

• Using <= causes index out of bounds
• Ignoring null checks on children
• Wrong method to check map keys

5. Given a Trie storing the words ["apple", "app", "bat", "bath"], which of the following search queries will return true and why? Options: A) search("app") B) search("bathe") C) search("bath") D) search("bat")

hard

A. All queries return true

B. Only "app" and "bat" return true

C. "app", "bat", and "bath" return true

D. Only "bathe" returns true

Solution

1. Step 1: Check each word in the Trie

   Words stored are "apple", "app", "bat", and "bath".

2. Step 2: Evaluate each search query

   "app" exists, so true; "bat" exists, so true; "bath" exists, so true; "bathe" does not exist, so false.

3. Final Answer:

   "app", "bat", and "bath" return true -> Option C

4. Quick Check:

   Search returns true only for stored words [OK]

Hint: Search true only for exact stored words [OK]

Common Mistakes:

• Assuming partial or longer words return true
• Confusing prefixes with full words
• Expecting non-inserted words to return true