Word Search in Trie in DSA Java - Execution Trace

Concept Flow - Word Search in Trie

Start at root node

↓

For each character in word

↓

Check if child node for character exists?

No→Word NOT found

Yes↓

Move to child node

↓

Repeat for next character

↓

After last character, check isEndOfWord?

Yes→Word FOUND

No↓

Word NOT found

Start from root, follow nodes for each character. If path breaks, word not found. If path ends and node marks word end, word found.

Execution Sample

DSA Java

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

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

Searches for a word in the trie by traversing nodes for each character and checking if the last node marks the end of a word.

Execution Table

Step	Operation	Current Character	Node Exists?	Move Pointer	Visual State
1	Start at root	-	Root exists	current = root	root
2	Check child for 'c'	c	Yes	current = node for 'c'	root -> c
3	Check child for 'a'	a	Yes	current = node for 'a'	root -> c -> a
4	Check child for 't'	t	Yes	current = node for 't'	root -> c -> a -> t
5	Check isEndOfWord at 't'	t	Yes	-	root -> c -> a -> t (isEndOfWord=true)
6	Return result	-	-	-	Word FOUND
7	Search for 'car'	-	-	-	root -> c -> a -> r (isEndOfWord=false)
8	Check isEndOfWord at 'r'	r	No	-	Word NOT found
9	Search for 'dog'	-	-	-	root -> d -> o -> g (isEndOfWord=true)
10	Check isEndOfWord at 'g'	g	Yes	-	Word FOUND
11	Search for 'cow'	-	-	-	root -> c -> o (null)
12	Check child for 'w'	w	No	-	Word NOT found

💡 Traversal stops when a character node is missing or after checking 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'
current_char	-	c	a	t	t	-
isEndOfWord	-	false	false	true	true	true

Key Moments - 3 Insights

Why do we check isEndOfWord after the last character?

Because a path may exist for all characters but the word might not end there. Step 5 and 8 show that even if nodes exist, isEndOfWord must be true to confirm the word.

What happens if a child node for a character is missing?

The search stops immediately and returns false. Step 12 shows that when 'w' child is missing, the word is not found.

Why do we move the current pointer to the child node each step?

To follow the path of characters in the trie. Steps 2 to 4 show current moving deeper to match each character.

Visual Quiz - 3 Questions

Look at the execution table, what is the node 'current' pointing to after Step 3?

A Node for 'a'

B Node for 'c'

C Node for 't'

D Root node

💡 Hint

Check the 'Move Pointer' and 'Visual State' columns at Step 3.

At which step does the search determine the word is NOT found because a child node is missing?

A Step 8

B Step 12

C Step 5

D Step 10

💡 Hint

Look for 'Node Exists?' column showing 'No' and 'Word NOT found' in Visual State.

If the word searched was 'car' and the node for 'r' had isEndOfWord = true, what would change in the execution table?

A Step 8 would show Word FOUND instead of NOT found

B Step 12 would change to Word FOUND

C Step 5 would change to Word NOT found

D No change in the table

💡 Hint

Check Step 8 where isEndOfWord is currently false causing NOT found.

Concept Snapshot

Word Search in Trie:
- Start at root node
- For each character, move to child node if exists
- If any character node missing, word not found
- After last character, check isEndOfWord flag
- Return true if isEndOfWord is true, else false

Full Transcript

This visual trace shows how to search a word in a trie. We start at the root node and for each character in the word, we check if a child node exists. If it does, we move the current pointer to that child node. If any character node is missing, the search stops and returns false. After processing all characters, we check if the current node marks the end of a word. If yes, the word is found; otherwise, it is not. The execution table tracks each step, the current character, whether the node exists, pointer moves, and the visual state of the trie path. Variable tracking shows how the current pointer and flags change. Key moments clarify why checking isEndOfWord is necessary and what happens when nodes are missing. The quiz tests understanding of pointer movement, termination conditions, and the importance of the end-of-word flag.

Practice

1. What is the main purpose of using a Trie data structure in word search problems?

easy

A. To perform arithmetic operations on words

B. To sort words alphabetically

C. To store words in a linked list

D. To efficiently store and search words by their prefixes

Solution

1. Step 1: Understand Trie structure

   A Trie stores characters of words in a tree-like structure where each node represents a character.

2. Step 2: Identify Trie usage in word search

   It allows quick prefix-based search, making it efficient to find words starting with given letters.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option D

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is all about prefix-based fast word search [OK]

Common Mistakes:

• Confusing Trie with sorting data structures
• Thinking Trie stores words as linked lists
• Assuming Trie performs arithmetic on words

2. Which of the following is the correct way to declare a Trie node class in Java?

easy

A. class TrieNode { char val; TrieNode[] children = new TrieNode[26]; boolean isWord; }

B. class TrieNode { int val; TrieNode children; boolean isWord; }

C. class TrieNode { String val; TrieNode[] children = new TrieNode[26]; }

D. class TrieNode { char val; List<TrieNode> children; boolean isWord; }

Solution

1. Step 1: Check data types for Trie node

   Each node stores a character, an array of 26 children for letters a-z, and a boolean to mark word end.

2. Step 2: Validate options

   class TrieNode { char val; TrieNode[] children = new TrieNode[26]; boolean isWord; } matches this structure exactly with char val, TrieNode[] children of size 26, and boolean isWord.

3. Final Answer:

   class TrieNode { char val; TrieNode[] children = new TrieNode[26]; boolean isWord; } -> Option A

4. Quick Check:

   Correct TrieNode declaration = class TrieNode { char val; TrieNode[] children = new TrieNode[26]; boolean isWord; } [OK]

Hint: Trie nodes use char + array of 26 children + boolean flag [OK]

Common Mistakes:

• Using int or String instead of char for node value
• Using single child instead of array for children
• Using List instead of fixed-size array for children

3. What will be the output of the following Java code snippet that inserts words into a Trie and searches for "cat"?

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

class Trie {
  TrieNode root = new TrieNode();

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

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

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

medium

A. false
false

B. true
false

C. true
true

D. false
true

Solution

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

   Both words are inserted character by character, marking the last node's isWord as true.

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

   "cat" exists with isWord true, so search returns true. "cap" path is missing 'p' node, so returns false.

3. Final Answer:

   true false -> Option B

4. Quick Check:

   Inserted words found = true, missing word = false [OK]

Hint: Search returns true only if full word path and isWord true [OK]

Common Mistakes:

• Assuming partial prefix returns true
• Not marking isWord correctly on insert
• Confusing character indexing in children array

4. Identify the bug in the following Trie search method and choose the correct fix:

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

medium

A. Initialize idx before loop

B. Return true inside the loop

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

D. Remove return statement inside loop

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= word.length(), which causes index out of bounds at last iteration.

2. Step 2: Fix loop condition

   Changing condition to i < word.length() prevents accessing invalid index and correctly iterates over characters.

3. Final Answer:

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

4. Quick Check:

   Loop boundary fix prevents index error [OK]

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

Common Mistakes:

• Using <= instead of < in loop condition
• Trying to fix by moving idx initialization
• Removing return inside loop causing wrong logic

5. Given a 2D board of characters and a list of words, which approach best uses a Trie to efficiently find all words present on the board? A sample board:

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Words: ["oath", "pea", "eat", "rain"]

hard

A. Build a Trie from words, then DFS on board checking prefixes in Trie

B. Check each word by scanning entire board without Trie

C. Use a hash set for words and scan board rows only

D. Sort words and board rows, then binary search each word

Solution

1. Step 1: Build Trie from given words

   Insert all words into a Trie to enable prefix checking during search.

2. Step 2: Perform DFS on board cells

   From each cell, explore neighbors recursively, checking if current path matches any prefix in Trie to prune search.

3. Step 3: Collect words found when Trie node marks word end

   This approach efficiently finds all words without redundant searches.

4. Final Answer:

   Build a Trie from words, then DFS on board checking prefixes in Trie -> Option A

5. Quick Check:

   Trie + DFS = efficient word search on board [OK]

Hint: Use Trie for prefix pruning during DFS on board [OK]

Common Mistakes:

• Searching words one by one scanning whole board
• Ignoring prefix pruning causing slow search
• Using sorting and binary search which doesn't fit 2D board