Trie Insert Operation in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting words into a Trie

What is the printed state of the Trie after inserting the words "cat", "car", and "dog" in order?

DSA Go

package main

import "fmt"

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

type Trie struct {
    root *TrieNode
}

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

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *Trie) Print(node *TrieNode, prefix string) {
    if node.isEnd {
        fmt.Println(prefix)
    }
    for ch, child := range node.children {
        t.Print(child, prefix+string(ch))
    }
}

func main() {
    trie := NewTrie()
    trie.Insert("cat")
    trie.Insert("car")
    trie.Insert("dog")
    trie.Print(trie.root, "")
}

A

car
cat
dog

B

cat
car
dog

C

dog
car
cat

D

cat
dog
car

💡 Hint

The Print function prints words in lexicographical order because it iterates over children map keys in Go's map iteration order, which is random. But since map iteration order is random, the output order depends on insertion and map iteration.

The Print function recursively prints all words stored in the Trie. Since Go's map iteration order is random, the output order is not guaranteed. However, in this code, the output is lex order due to insertion order and map iteration in this run: 'car', 'cat', 'dog'.

🧠 Conceptual

intermediate

Number of nodes after inserting words in a Trie

After inserting the words "apple", "app", and "ape" into an empty Trie, how many nodes does the Trie contain (including the root node)?

A 7

B 8

C 6

D 9

💡 Hint

Count shared prefixes only once.

The root node plus nodes for 'a', 'p', 'p', 'l', 'e', and 'e' for 'ape' and 'app' share nodes. Total nodes: root + a + p + p + l + e + e = 7 nodes.

🔧 Debug

advanced

Identify the error in Trie Insert method

What error will this Trie Insert method cause when inserting the word "bat"?

DSA Go

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] != nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

A Runtime panic: assignment to nil map

B Nil pointer dereference panic

C No error, inserts correctly

D Infinite loop

💡 Hint

Check the condition that creates new nodes.

The condition incorrectly checks if node.children[ch] != nil before creating a new node, so it overwrites existing nodes and tries to access nil pointers causing nil pointer dereference panic.

📝 Syntax

advanced

Which option correctly defines the TrieNode struct with children map?

Select the correct Go struct definition for a TrieNode that holds children nodes and an end-of-word flag.

A

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

B

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

C

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

D

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

💡 Hint

Children keys should be characters, not strings or ints.

The children map keys must be rune (character) to represent each letter. Option D uses map[rune]*TrieNode which is correct.

🚀 Application

expert

Resulting Trie after inserting and searching words

After inserting "tree", "trie", "algo", and "algo" again into an empty Trie, which words will be found by searching for "trie" and "alg"?

DSA Go

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
}

A "trie" found: true, "alg" found: true

B "trie" found: false, "alg" found: true

C "trie" found: true, "alg" found: false

D "trie" found: false, "alg" found: false

💡 Hint

"alg" is a prefix but not a complete inserted word.

The Search method returns true only if the full word is inserted and marked isEnd true. "trie" was inserted, so found true. "alg" is prefix of "algo" but not a complete word, so found false.