Trie Search Operation in DSA Java

Mental Model

A trie stores words by branching letters step-by-step. Searching means following these letter branches to see if a word exists.

Analogy: Imagine a tree where each branch is a letter. To find a word, you walk down the branches matching each letter until you reach the end of the word.

root
 ↓
 [c] -> [a] -> [t] (end)
           ↓
          [r] -> [s] (end)

Here, words 'cat' and 'cars' share the first two letters.

Dry Run Walkthrough

Input: Trie contains words: 'cat', 'cars'. Search for 'car'.

Goal: Check if 'car' exists in the trie.

Step 1: Start at root, check for 'c' branch

root -> [c] -> [a] -> [t] (end), [r] -> [s] (end)

Why: We must find the first letter 'c' to continue searching.

Step 2: Move to 'c' node, check for 'a' branch

root -> c -> [a] -> [t] (end), [r] -> [s] (end)

Why: Next letter 'a' must be found under 'c' to continue.

Step 3: Move to 'a' node, check for 'r' branch

root -> c -> a -> [t] (end), [r] -> [s] (end)

Why: Next letter 'r' must be found under 'a' to continue.

Step 4: Move to 'r' node, check if this node marks end of word

root -> c -> a -> r -> [s] (end), 'r' node is not end

Why: We found all letters but 'r' node is not end, so 'car' is not a complete word.

Result:

root -> c -> a -> r -> s (end)
Search result: 'car' not found (prefix only)

Annotated Code

DSA Java

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

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

public class Trie {
    private final TrieNode root;

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

    public void insert(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            curr.children.putIfAbsent(ch, new TrieNode()); // add branch if missing
            curr = curr.children.get(ch); // move down the branch
        }
        curr.isEndOfWord = true; // mark end of word
    }

    public boolean search(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                return false; // letter missing, word not found
            }
            curr = curr.children.get(ch); // move down the branch
        }
        return curr.isEndOfWord; // true if end of word, false if prefix only
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("cars");

        System.out.println(trie.search("car"));
        System.out.println(trie.search("cat"));
        System.out.println(trie.search("cars"));
        System.out.println(trie.search("cap"));
    }
}

curr.children.putIfAbsent(ch, new TrieNode()); // add branch if missing

create new branch for letter if it does not exist

curr = curr.children.get(ch); // move down the branch

advance current node to next letter branch

curr.isEndOfWord = true; // mark end of word

mark node as end of a complete word

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

stop search if letter branch missing

return curr.isEndOfWord; // true if word ends here

confirm word exists only if node marks end

Output

false

true

true

false

Complexity Analysis

Time: O(m) because search checks each letter of the word once, where m is word length

Space: O(1) for search since no extra space grows with input during search

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster as it depends only on word length, not number of words

Edge Cases

search empty string

returns false because empty word is not stored

DSA Java

return curr.isEndOfWord; // true if word ends here

search word not inserted

returns false when letter branch missing

DSA Java

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

search prefix of inserted word

returns false if prefix node is not end of word

DSA Java

return curr.isEndOfWord; // true if word ends here

When to Use This Pattern

When you need to quickly check if a word or prefix exists among many words, use trie search because it follows letter branches efficiently.

Common Mistakes

Mistake: Returning true if all letters found without checking if node marks end of word
Fix: Always check isEndOfWord to confirm full word presence, not just prefix

Mistake: Not checking if letter branch exists before moving down
Fix: Check children.containsKey before accessing to avoid errors and wrong results

Summary

It checks if a word exists by following letter branches in the trie.

Use it when you want fast word lookups among many stored words.

The key is to confirm the last letter node marks the end of a complete word.

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