Trie Search Operation in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the current node marks the end of a word in the Trie.

DSA Java

return current.[1];

Drag options to blanks, or click blank then click option'

AisRoot

BhasChild

CisEndOfWord

DisLeaf

Attempts:

3 left

💡 Hint

Common Mistakes

Using a method or property that checks for children instead of word end.

Confusing root or leaf node properties with end of word.

The isEndOfWord boolean indicates if the current node marks the end of a stored word in the Trie.

2fill in blank

medium

Complete the code to move to the child node corresponding to the current character during search.

DSA Java

current = current.children[[1] - 'a'];

Drag options to blanks, or click blank then click option'

Ac

Bi

Cindex

Dchar

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong variable name for the character.

Using an integer index variable instead of the character.

We use the character c from the word to find the correct child node by subtracting 'a' to get the index.

3fill in blank

hard

Fix the error in the search loop condition to correctly iterate over the characters of the word.

DSA Java

for (int i = 0; i [1] word.length(); i++) {

Drag options to blanks, or click blank then click option'

A<=

B<

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= causes an index out of bounds error.

Using > or >= causes the loop to never run.

The loop should run while i is less than the length of the word to avoid index out of bounds.

4fill in blank

hard

Fill both blanks to check if the child node exists and move to it during search.

DSA Java

if (current.children[[1] - 'a'] == [2]) {
    return false;
}

Drag options to blanks, or click blank then click option'

Ac

Bnull

Ci

Dtrue

Attempts:

3 left

💡 Hint

Common Mistakes

Checking against true instead of null.

Using the wrong variable for the character index.

We check if the child node for character c is null. If yes, the word is not in the Trie.

5fill in blank

hard

Fill all three blanks to complete the search method that returns true if the word exists in the Trie.

DSA Java

public boolean search(String word) {
    TrieNode current = root;
    for (int [1] = 0; [2] < word.length(); [3]++) {
        char c = word.charAt(i);
        if (current.children[c - 'a'] == null) {
            return false;
        }
        current = current.children[c - 'a'];
    }
    return current.isEndOfWord;
}

Drag options to blanks, or click blank then click option'

Ai

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names in the loop parts.

Using incorrect loop syntax causing errors.

The loop variable i is used for initialization, condition, and increment to iterate over the word characters.

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