Word Search in Trie in DSA Go - Execution Trace

Concept Flow - Word Search in Trie

Start at root node

↓

For each letter in word

↓

Check if letter child exists?

No→Word NOT found

Yes↓

Move to child node

↓

Repeat for next letter

↓

After last letter, check isWord flag

↓

If isWord true -> Word FOUND

↓

Else -> Word NOT found

Start from the root and check each letter of the word in the trie nodes. If all letters exist and the last node marks a word end, the word is found.

Execution Sample

DSA Go

func Search(root *TrieNode, word string) bool {
    node := root
    for _, ch := range word {
        if node.children[ch-'a'] == nil {
            return false
        }
        node = node.children[ch-'a']
    }
    return node.isWord
}

This code searches for a word in a trie by traversing nodes for each letter and checking if the final node marks a complete word.

Execution Table

Step	Operation	Current Letter	Node Children Check	Move Pointer	Visual State
1	Start at root	-	Root has child 'c' for 'c'?	Move to child 'c'	root -> c
2	Check letter 'a'	a	Node 'c' has child 'a'?	Move to child 'a'	root -> c -> a
3	Check letter 't'	t	Node 'a' has child 't'?	Move to child 't'	root -> c -> a -> t
4	End of word	-	Node 't' isWord?	No move	root -> c -> a -> t (isWord=true)
5	Result	-	-	-	Word FOUND

💡 Traversal ends after last letter; isWord flag true means word found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
node	root	node at 'c'	node at 'a'	node at 't'	node at 't'	node at 't'
current letter	-	c	a	t	-	-

Key Moments - 3 Insights

Why do we check if the child node exists before moving?

Because if the child node for the current letter does not exist (see execution_table step 2), the word cannot be in the trie, so we stop searching.

Why do we check the isWord flag at the last node?

Because the path may exist but not represent a complete word. Only if isWord is true (execution_table step 4) do we confirm the word is stored.

What happens if the word is empty?

The loop does not run, so we check if root.isWord is true. Usually root.isWord is false, so empty word is not found.

Visual Quiz - 3 Questions

Look at the execution_table, what is the node pointer after checking letter 'a'?

A Node at 't'

B Node at 'c'

C Node at 'a'

D Root node

💡 Hint

Check the 'Move Pointer' column at step 2 in execution_table.

At which step does the search confirm the word is found?

A Step 3

B Step 5

C Step 2

D Step 4

💡 Hint

Look at the 'Result' row in execution_table where word FOUND is stated.

If the node for letter 't' was missing, what would happen?

A Search returns false at step 3

B Search continues to next letter

C Search returns true

D Search checks isWord flag

💡 Hint

Refer to 'Node Children Check' and 'Operation' columns in execution_table step 3.

Concept Snapshot

Word Search in Trie:
- Start at root node
- For each letter, check if child node exists
- Move pointer to child node if exists
- After last letter, check isWord flag
- If true, word found; else not found

Full Transcript

To search a word in a trie, start at the root node. For each letter in the word, check if the current node has a child node for that letter. If not, the word is not in the trie. If yes, move to that child node and continue. After processing all letters, check if the last node marks the end of a word (isWord flag). If it does, the word is found; otherwise, it is not. This process ensures only complete words stored in the trie are recognized.

Practice

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

easy

A. To reverse words quickly

B. To sort words alphabetically

C. To store words efficiently for quick prefix-based searches

D. To count the frequency of words

Solution

1. Step 1: Understand Trie structure

   A Trie stores characters of words in a tree form, sharing prefixes.

2. Step 2: Identify Trie use in word search

   This structure allows fast prefix checks and word existence queries.

3. Final Answer:

   To store words efficiently for quick prefix-based searches -> Option C

4. Quick Check:

   Trie = prefix search efficiency [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie counts word frequency
• Assuming Trie reverses words

2. Which of the following Go code snippets correctly initializes an empty Trie node struct with a children map and end-of-word flag?

easy

A. type TrieNode struct { children map[string]TrieNode; isEnd bool }
root := TrieNode{children: map[string]TrieNode{}, isEnd: false}

B. type TrieNode struct { children []TrieNode; isEnd int }
root := TrieNode{children: []TrieNode{}, isEnd: 0}

C. type TrieNode struct { children map[rune]TrieNode; isEnd bool }
root := &TrieNode{children: make(map[rune]TrieNode), isEnd: false}

D. type TrieNode struct { children map[rune]*TrieNode; isEnd bool }
root := &TrieNode{children: make(map[rune]*TrieNode), isEnd: false}

Solution

1. Step 1: Check struct field types

   Children should be a map from rune to pointer to TrieNode for dynamic nodes.

2. Step 2: Verify initialization syntax

   Use make(map[rune]*TrieNode) and isEnd as bool with false initial value.

3. Final Answer:

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } root := &TrieNode{children: make(map[rune]*TrieNode), isEnd: false} -> Option D

4. Quick Check:

   Correct map and pointer usage = type TrieNode struct { children map[rune]*TrieNode; isEnd bool } root := &TrieNode{children: make(map[rune]*TrieNode), isEnd: false} [OK]

Hint: Use map[rune]*TrieNode and make() to initialize children [OK]

Common Mistakes:

• Using slice instead of map for children
• Using non-pointer TrieNode in map values
• Incorrect map key type (string instead of rune)

3. Given the following Go code snippet for searching a word in a Trie, what will be the output if the word "cat" is searched after inserting "car" and "cat"?

func (t *TrieNode) Search(word string) bool {
    node := t
    for _, ch := range word {
        if _, ok := node.children[ch]; !ok {
            return false
        }
        node = node.children[ch]
    }
    return node.isEnd
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Understand insertion of "car" and "cat"

   Both words share prefix 'ca', nodes created for 'c', 'a', then separate nodes for 'r' and 't' with isEnd true.

2. Step 2: Trace search for "cat"

   Traverse nodes for 'c', 'a', 't' successfully, last node has isEnd true, so returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Word inserted and found = true [OK]

Hint: Search returns true if last node's isEnd is true [OK]

Common Mistakes:

• Assuming search returns true for prefixes only
• Confusing isEnd flag usage
• Thinking search returns true if partial path exists

4. Identify the bug in the following Go code snippet for searching a word in a Trie:

func (t *TrieNode) Search(word string) bool {
    node := t
    for _, ch := range word {
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return true
}

medium

A. Returns true even if the word is only a prefix, not a full word

B. Panics if children map is nil

C. Does not check for nil children map before access

D. Incorrect loop variable type causes compilation error

Solution

1. Step 1: Analyze search return condition

   Function returns true after traversing all characters without checking isEnd flag.

2. Step 2: Understand consequence of missing isEnd check

   Words that are prefixes but not complete words will incorrectly return true.

3. Final Answer:

   Returns true even if the word is only a prefix, not a full word -> Option A

4. Quick Check:

   Missing isEnd check causes false positives [OK]

Hint: Always check isEnd after traversal to confirm full word [OK]

Common Mistakes:

• Forgetting to check isEnd flag
• Assuming traversal success means word exists
• Ignoring nil map checks (not in this code)

5. You have a list of words: ["apple", "app", "application", "bat", "bath", "baton"]. You want to build a Trie and then search for the word "bat". Which of the following statements is true about the search result and the Trie structure after insertion?

hard

A. Searching "bat" returns false because "bat" is a prefix of "bath" and "baton"

B. Searching "bat" returns true; nodes for 'b', 'a', 't' share prefixes with other words

C. Trie stores each word as a separate branch without shared nodes

D. Searching "bat" returns true only if "bat" is inserted last

Solution

1. Step 1: Insert all words into Trie

   Words share prefixes: "app" and "apple" share 'app', "bat", "bath", "baton" share 'bat'.

2. Step 2: Search for "bat"

   Since "bat" is inserted, its node's isEnd is true, so search returns true.

3. Final Answer:

   Searching "bat" returns true; nodes for 'b', 'a', 't' share prefixes with other words -> Option B

4. Quick Check:

   Shared prefix nodes and isEnd true = Searching "bat" returns true; nodes for 'b', 'a', 't' share prefixes with other words [OK]

Hint: Shared prefixes save space; isEnd marks full words [OK]

Common Mistakes:

• Thinking prefix words are not found
• Assuming separate branches for each word
• Believing insertion order affects search result