Trie Search Operation in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths down the tree represent words.

beginner

How does the search operation work in a Trie?

The search operation checks each character of the word by moving down the Trie nodes. If all characters are found and the last node marks the end of a word, the search returns true; otherwise, false.

beginner

What does it mean if a node in a Trie has a 'isEndOfWord' flag set to true?

It means that the path from the root to this node forms a complete word stored in the Trie.

intermediate

Why is Trie search operation efficient for prefix-based queries?

Because Trie nodes represent prefixes, searching for words with a common prefix shares the same path, making prefix queries fast and memory efficient.

beginner

What happens if a character in the search word is not found in the Trie nodes?

The search operation immediately returns false because the word does not exist in the Trie.

In a Trie search operation, what does it mean if you reach a node where the next character is missing?

A The word is not present in the Trie

B The word is definitely present

C The Trie is empty

D The search should restart from root

If the next character node is missing, the word cannot be found in the Trie.

What does the 'isEndOfWord' flag indicate in a Trie node during search?

A The node has no children

B The node is the root

C The node marks the end of a valid word

D The node is a leaf node

The 'isEndOfWord' flag shows that the path to this node forms a complete stored word.

Which of the following best describes the time complexity of searching a word in a Trie?

A O(log n), where n is the number of words

B O(n), where n is the length of the word

C O(n^2), where n is the length of the word

D O(1)

Search time depends on the length of the word, checking each character once.

If a Trie contains the words 'cat' and 'car', what will the search for 'ca' return?

A Depends on implementation

B True

C Error

D False

'ca' is a prefix but not a complete word, so search returns false unless 'ca' is explicitly inserted.

What is the first step in searching a word in a Trie?

A Traverse the Trie nodes matching each character of the word

B Insert the word into the Trie

C Check if the root node is null

D Delete the word from the Trie

Search starts by traversing nodes matching each character in order.

Explain step-by-step how the search operation works in a Trie for a given word.

Think of walking down a path matching letters.

Describe why Trie search is efficient for prefix matching compared to other data structures.

Imagine a tree where branches represent letters.

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