Word Search in Trie in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Search in Trie after Insertions

What is the output of the following Go code that inserts words into a Trie and searches for a specific word?

DSA Go

package main

import "fmt"

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}

func NewTrieNode() *TrieNode {
    return &TrieNode{children: make(map[rune]*TrieNode)}
}

func NewTrie() *Trie {
    return &Trie{root: NewTrieNode()}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if _, ok := node.children[ch]; !ok {
            node.children[ch] = NewTrieNode()
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

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

func main() {
    trie := NewTrie()
    trie.Insert("go")
    trie.Insert("gone")
    trie.Insert("gopher")
    fmt.Println(trie.Search("go"))
    fmt.Println(trie.Search("gone"))
    fmt.Println(trie.Search("goph"))
}

A

true
true
true

B

true
true
false

C

false
true
false

D

true
false
false

💡 Hint

Remember that Search returns true only if the word is fully present and marked as an end.

The words "go" and "gone" are inserted fully and marked as end nodes, so searching them returns true. "goph" is a prefix but not a complete word inserted, so search returns false.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the role of the 'isEnd' boolean in a Trie node?

A It marks the node as the end of a valid inserted word.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It indicates if the node has any children nodes.

💡 Hint

Think about how the Trie distinguishes between prefixes and complete words.

The 'isEnd' flag marks that the path to this node forms a complete word inserted into the Trie.

🔧 Debug

advanced

Identify the Bug in Trie Search Method

What error will the following Go code produce when searching for a word not in the Trie?

DSA Go

func (t *Trie) Search(word string) bool {
    node := t.root
    for _, ch := range word {
        node = node.children[ch]
    }
    return node.isEnd
}

A compilation error: missing if check

B returns false correctly

C runtime error: invalid memory address or nil pointer dereference

D returns true incorrectly

💡 Hint

What happens if the character is not found in children map?

The code does not check if the child node exists before accessing it, so accessing a missing key returns nil and causes a runtime panic.

🚀 Application

advanced

Number of Words Stored in Trie

Given a Trie with the words inserted: ["cat", "car", "cart", "dog", "dot"], how many words does the Trie contain?

A 5

B 6

C 3

D 4

💡 Hint

Count each unique complete word inserted.

All five words are distinct and inserted fully, so the Trie contains 5 words.

❓ Predict Output

expert

Output of Trie Search with Prefixes and Words

What is the output of this Go program that inserts words and searches for prefixes and words?

DSA Go

package main

import "fmt"

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}

func NewTrieNode() *TrieNode {
    return &TrieNode{children: make(map[rune]*TrieNode)}
}

func NewTrie() *Trie {
    return &Trie{root: NewTrieNode()}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if _, ok := node.children[ch]; !ok {
            node.children[ch] = NewTrieNode()
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

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

func main() {
    trie := NewTrie()
    trie.Insert("apple")
    trie.Insert("app")
    trie.Insert("application")
    fmt.Println(trie.Search("app"))
    fmt.Println(trie.Search("apple"))
    fmt.Println(trie.Search("appl"))
    fmt.Println(trie.Search("application"))
}

A

false
true
false
true

B

true
false
false
true

C

true
true
true
true

D

true
true
false
true

💡 Hint

Only words fully inserted and marked as end return true.

"app", "apple", and "application" are inserted words. "appl" is a prefix but not a complete word, so search returns false for it.

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