Word Search in Trie in DSA Go

Mental Model

A trie stores words by sharing common prefixes, making it easy to check if a word exists by following letters step-by-step.

Analogy: Imagine a tree of roads where each road sign is a letter. To find a word, you follow the signs letter by letter until you reach the end of the word.

root
 ↓
 a -> b -> c (end)
  ↓
  d (end)

Each arrow -> shows the next letter link.
'end' marks a complete word.

Dry Run Walkthrough

Input: Insert words: "cat", "car", "dog"; Search for "car"

Goal: Check if the word "car" exists in the trie

Step 1: Insert 'cat' letter by letter

root -> c -> a -> t [end]
root -> null

Why: Build path for 'cat' so we can find it later

Step 2: Insert 'car' letter by letter, sharing prefix 'ca'

root -> c -> a -> t [end]
               ↓
               r [end]

Why: Reuse 'ca' nodes, add 'r' to mark 'car'

Step 3: Insert 'dog' letter by letter

root -> c -> a -> t [end]
               ↓
               r [end]
root -> d -> o -> g [end]

Why: Add new branch for 'dog'

Step 4: Search for 'car' by following letters c -> a -> r

root -> c -> a -> r [end]

Why: All letters found and 'r' marks end of word, so 'car' exists

Result:

root -> c -> a -> t [end]
               ↓
               r [end]
root -> d -> o -> g [end]
Search result: true

Annotated Code

DSA Go

package main

import "fmt"

// TrieNode represents each node in the trie
type TrieNode struct {
	children map[rune]*TrieNode
	isEnd bool
}

// Trie structure with root node
type Trie struct {
	root *TrieNode
}

// NewTrieNode creates a new trie node
func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

// NewTrie creates a new trie
func NewTrie() *Trie {
	return &Trie{root: NewTrieNode()}
}

// Insert adds a word to the trie
func (t *Trie) Insert(word string) {
	curr := t.root
	for _, ch := range word {
		if _, ok := curr.children[ch]; !ok {
			curr.children[ch] = NewTrieNode() // create node if missing
		}
		curr = curr.children[ch] // move to next node
	}
	curr.isEnd = true // mark end of word
}

// Search checks if a word exists in the trie
func (t *Trie) Search(word string) bool {
	curr := t.root
	for _, ch := range word {
		if _, ok := curr.children[ch]; !ok {
			return false // letter missing, word not found
		}
		curr = curr.children[ch] // move to next node
	}
	return curr.isEnd // true if end of word
}

func main() {
	trie := NewTrie()
	trie.Insert("cat")
	trie.Insert("car")
	trie.Insert("dog")

	fmt.Println(trie.Search("car"))
}

if _, ok := curr.children[ch]; !ok {

check if current letter node exists

curr.children[ch] = NewTrieNode() // create node if missing

create new node for letter if missing

curr = curr.children[ch] // move to next node

advance current pointer to next letter node

curr.isEnd = true // mark end of a complete word

mark node as end of a complete word

if _, ok := curr.children[ch]; !ok { return false }

if letter missing during search, word not found

return curr.isEnd // true if end of word

return true only if last letter marks word end

Output

true

Complexity Analysis

Time: O(m) because we process each of the m letters in the word once during insert or search

Space: O(m) for insert because new nodes may be created for each letter; search uses O(1) extra space

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster as it avoids scanning all words

Edge Cases

search for empty string

returns false because empty word is not inserted

DSA Go

return curr.isEnd // true if end of word

search for word not inserted

returns false as missing letter node detected

DSA Go

if _, ok := curr.children[ch]; !ok { return false }

insert duplicate word

no new nodes created, end marker remains true

DSA Go

curr.isEnd = true // mark end of word

When to Use This Pattern

When you need to quickly check if words or prefixes exist in a large set, use a trie because it shares common prefixes and speeds up search.

Common Mistakes

Mistake: Not marking the end of a word, causing search to return true for prefixes instead of full words
Fix: Always set isEnd = true at the last node of inserted words

Mistake: Not checking if a child node exists before moving, causing runtime errors
Fix: Check if child node exists before moving; if missing, create node (insert) or return false (search)

Summary

Stores words letter by letter sharing prefixes to enable fast word search.

Use when you want to check if words exist efficiently among many words.

The key is to follow letters step-by-step and mark where words end.

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