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.