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.