Trie Search Operation in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Search for Existing Word

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

DSA Go

package main
import "fmt"

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

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

// Initialize a new TrieNode
func newNode() *TrieNode {
    return &TrieNode{children: make(map[rune]*TrieNode)}
}

// Insert a word into the Trie
func (t *Trie) Insert(word string) {
    current := t.root
    for _, ch := range word {
        if _, ok := current.children[ch]; !ok {
            current.children[ch] = newNode()
        }
        current = current.children[ch]
    }
    current.isEnd = true
}

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

func main() {
    trie := &Trie{root: newNode()}
    trie.Insert("cat")
    trie.Insert("car")
    trie.Insert("dog")
    fmt.Println(trie.Search("cat"))
}

A panic: runtime error

B false

C Compilation error

D true

💡 Hint

Think about whether the word "cat" was inserted before searching.

The word "cat" was inserted into the Trie, so searching for it returns true.

❓ Predict Output

intermediate

Output of Trie Search for Non-Existing Word

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

DSA Go

package main
import "fmt"

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

type Trie struct {
    root *TrieNode
}

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

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

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

func main() {
    trie := &Trie{root: newNode()}
    trie.Insert("cat")
    trie.Insert("car")
    trie.Insert("dog")
    fmt.Println(trie.Search("bat"))
}

A Compilation error

B true

C false

D panic: runtime error

💡 Hint

Check if "bat" was inserted before searching.

The word "bat" was not inserted, so searching returns false.

🧠 Conceptual

advanced

Understanding Trie Search Behavior

In a Trie, what does it mean if the search for a word returns true?

A The Trie is empty.

B The word exists in the Trie and ends at a node marked as end of word.

C The word does not exist but shares some characters with words in the Trie.

D The word is a prefix of some word in the Trie but not necessarily a complete word.

💡 Hint

Think about the isEnd flag in Trie nodes.

A search returns true only if the word is fully present and the last character node is marked as end of a word.

❓ Predict Output

advanced

Output of Trie Search with Partial Word

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

DSA Go

package main
import "fmt"

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

type Trie struct {
    root *TrieNode
}

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

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

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

func main() {
    trie := &Trie{root: newNode()}
    trie.Insert("cat")
    trie.Insert("car")
    trie.Insert("dog")
    fmt.Println(trie.Search("ca"))
}

A false

B true

C Compilation error

D panic: runtime error

💡 Hint

Is "ca" marked as a complete word in the Trie?

The search returns false because "ca" is only a prefix, not a complete word inserted.

🧠 Conceptual

expert

Why is the isEnd Flag Important in Trie Search?

Why do Trie nodes have an isEnd flag, and what would happen if it was missing during search?

A It marks the end of a complete word; without it, search cannot distinguish between prefixes and full words.

B It stores the frequency of words; without it, search would be slower.

C It points to the parent node; without it, traversal would be impossible.

D It stores the character value; without it, nodes would be empty.

💡 Hint

Think about how the Trie differentiates between a word and its prefix.

The isEnd flag tells if a node marks the end of a valid word. Without it, search would wrongly return true for prefixes that are not complete words.

Practice

1. What does the search operation in a Trie data structure check for?

easy

A. The number of words stored in the Trie

B. If the Trie is empty

C. If a given word exists in the Trie

D. The length of the longest word in the Trie

Solution

1. Step 1: Understand the purpose of Trie search

   The search operation in a Trie is designed to check if a specific word is stored in the Trie.

2. Step 2: Differentiate from other Trie operations

   Other operations like counting words or checking emptiness are not the purpose of search.

3. Final Answer:

   If a given word exists in the Trie -> Option C

4. Quick Check:

   Trie search checks word existence [OK]

Hint: Search checks if the exact word is stored [OK]

Common Mistakes:

• Confusing search with counting words
• Thinking search checks Trie emptiness
• Assuming search returns word length

2. Which of the following is the correct way to check if a character node exists in a Trie map in Go?

easy

A. if node.children[char] != nil

B. if node.children[char] == nil

C. if node.children.contains(char)

D. if node.children.has(char)

Solution

1. Step 1: Recall Go map access syntax

   In Go, to check if a key exists in a map, you check if the value is not nil (for pointer or map values).

2. Step 2: Apply to Trie children map

   Trie children are stored in a map from rune to *TrieNode, so checking if node.children[char] != nil confirms existence.

3. Final Answer:

   if node.children[char] != nil -> Option A

4. Quick Check:

   Go map key exists check [OK]

Hint: Check map key by comparing to nil in Go [OK]

Common Mistakes:

• Using contains or has methods (not in Go maps)
• Checking for equality to nil incorrectly
• Confusing map key existence with value presence

3. Consider the following Go code snippet for searching a word in a Trie:

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

What will be the output of Search("cat") if the Trie contains the words "car", "cat", and "cap"?

medium

A. compilation error

B. true

C. runtime error

D. false

Solution

1. Step 1: Trace the search for "cat" in the Trie

   The loop checks each character 'c', 'a', 't' in order. Since "cat" is inserted, all nodes exist and node.isEnd is true at 't'.

2. Step 2: Return value after traversal

   Because node.isEnd is true at the last character, the function returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Word "cat" exists in Trie = true [OK]

Hint: Search returns true if last node marks word end [OK]

Common Mistakes:

• Ignoring isEnd flag and returning true always
• Assuming false if any child exists
• Confusing runtime errors with nil checks

4. The following Go code for Trie search has a bug. What is the error?

func (t *Trie) Search(word string) bool {
    node := t.root
    for i := 0; i <= len(word); i++ {
        ch := rune(word[i])
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return node.isEnd
}

medium

A. Missing check for empty Trie root

B. Incorrect rune conversion for characters

C. Returning wrong boolean value

D. Index out of range error due to loop condition

Solution

1. Step 1: Analyze the loop condition

   The loop runs from i = 0 to i <= len(word), which means it tries to access word[len(word)] causing index out of range error.

2. Step 2: Correct loop boundary

   The loop should run with i < len(word) to avoid accessing beyond the string length.

3. Final Answer:

   Index out of range error due to loop condition -> Option D

4. Quick Check:

   Loop boundary error causes runtime panic [OK]

Hint: Use i < len(word), not i <= len(word) in loops [OK]

Common Mistakes:

• Using <= instead of < in loop
• Ignoring string length limits
• Assuming rune conversion causes error

5. You want to modify the Trie search function to support prefix search (check if any word starts with the given prefix). Which change is correct?

hard

A. Return true immediately after traversing all prefix characters without checking isEnd

B. Return true only if isEnd is true at last prefix character

C. Return false if any character node is missing, else return false always

D. Return true only if prefix length equals word length stored

Solution

1. Step 1: Understand prefix search goal

   Prefix search should return true if the prefix exists as a path in the Trie, regardless of isEnd flag.

2. Step 2: Modify search to return true after prefix traversal

   After checking all prefix characters exist, return true immediately without checking isEnd.

3. Final Answer:

   Return true immediately after traversing all prefix characters without checking isEnd -> Option A

4. Quick Check:

   Prefix search ignores isEnd, returns true if path exists [OK]

Hint: For prefix, return true after full prefix traversal [OK]

Common Mistakes:

• Checking isEnd for prefix search
• Returning false even if prefix path exists
• Confusing prefix length with word length