Trie Search Operation in DSA Java - Execution Trace

Concept Flow - Trie Search Operation

Start at root node

↓

For each character in word

↓

Check if child node for character exists

↓

Move to child

↓

Repeat for next char

↓

After last char, check isEndOfWord

↓

Word found

The search starts at the root and moves through child nodes for each character. If any character node is missing, the word is not found. After the last character, the node's end marker confirms the word's presence.

Execution Sample

DSA Java

boolean search(String word) {
  TrieNode current = root;
  for (char ch : word.toCharArray()) {
    if (!current.children.containsKey(ch)) return false;
    current = current.children.get(ch);
  }
  return current.isEndOfWord;
}

This code checks each character of the word in the trie nodes and returns true if the word exists fully with an end marker.

Execution Table

Step	Operation	Character	Node Exists?	Move Pointer	Visual State
1	Start at root	-	N/A	current = root	root
2	Check 'c'	c	Yes	current = node_c	root → c
3	Check 'a'	a	Yes	current = node_a	root → c → a
4	Check 't'	t	Yes	current = node_t	root → c → a → t
5	Check end of word	-	N/A	Check isEndOfWord	Node 't' isEndOfWord = true
6	Return result	-	N/A	Return true	Word 'cat' found
7	Search for 'car'	r	No	Return false	No node 'r' after 'a'

💡 Search stops when a character node is missing or after confirming isEndOfWord at last character.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	root	node_c	node_a	node_t	node_t	node_t or null
Character	-	c	a	t	-	-
isEndOfWord	N/A	N/A	N/A	N/A	true	true or false

Key Moments - 3 Insights

Why do we check isEndOfWord after the last character?

Because nodes can represent prefixes, not full words. Checking isEndOfWord confirms the word ends here (see execution_table step 5).

What happens if a character node does not exist during traversal?

The search immediately returns false since the word cannot be formed (see execution_table step 7).

Why do we move the current pointer only if the child node exists?

Moving current to a non-existent node would cause errors. We only move if the node exists to continue traversal (see execution_table steps 2-4).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 3?

A node_a

B node_c

C node_t

D root

💡 Hint

Check the 'current' column in execution_table row for step 3.

At which step does the search determine the word 'cat' is found?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look for the step where the function returns true in execution_table.

If the trie did not mark node 't' as end of word, what would be the search result for 'cat'?

A True

B False

C Error

D Partial match

💡 Hint

Refer to the isEndOfWord check in execution_table step 5.

Concept Snapshot

Trie Search Operation:
- Start at root node
- For each character, move to child node if exists
- If any character missing, return false
- After last char, check isEndOfWord
- Return true if word ends here, else false

Full Transcript

The trie search operation begins at the root node. For each character in the word, it checks if a child node exists. If yes, it moves the current pointer to that node. If any character node is missing, the search returns false immediately. After processing all characters, it checks if the current node marks the end of a word. If yes, the word exists in the trie and returns true; otherwise, false. This ensures only complete words are found, not just prefixes.

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