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.

Practice

1. What is the main purpose of the Insert operation in a Trie data structure?

easy

A. To delete a word from the Trie

B. To add a new word by creating nodes for each character

C. To search for a word in the Trie

D. To count the total words stored in the Trie

Solution

1. Step 1: Understand the Insert operation

   The Insert operation adds a word by creating nodes for each character if they don't exist.

2. Step 2: Differentiate from other operations

   Deleting removes words, searching finds words, counting totals words. Insert specifically adds words.

3. Final Answer:

   To add a new word by creating nodes for each character -> Option B

4. Quick Check:

   Insert = Add word nodes [OK]

Hint: Insert means adding nodes for each character [OK]

Common Mistakes:

• Confusing insert with search or delete
• Thinking insert counts words
• Assuming insert modifies existing words

2. Which of the following is the correct way to declare a Trie node struct in Go for insertion?

easy

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

B. type TrieNode struct { children []int; isEnd int }

C. type TrieNode struct { children map[string]int; isEnd string }

D. type TrieNode struct { children []string; isEnd bool }

Solution

1. Step 1: Identify correct children type for TrieNode

   Children should map characters (rune) to TrieNode pointers for branching.

2. Step 2: Check isEnd type

   isEnd is a boolean indicating if node ends a word.

3. Final Answer:

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } -> Option A

4. Quick Check:

   Children map[rune]*TrieNode and isEnd bool [OK]

Hint: Children map with rune keys and bool isEnd [OK]

Common Mistakes:

• Using slice instead of map for children
• Wrong data types for children or isEnd
• Using string keys instead of rune

3. What will be the output after inserting the words "cat" and "car" into an empty Trie and then checking if the node for 'a' under 'c' has children?

medium

A. nil

B. false

C. true

D. runtime error

Solution

1. Step 1: Insert "cat" and "car" into Trie

   Both words share prefix 'c' -> 'a'. After insertion, node 'a' has children 't' and 'r'.

2. Step 2: Check if node 'a' under 'c' has children

   Since 'a' node has two children nodes ('t' and 'r'), it has children, so true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Shared prefix node has children = true [OK]

Hint: Shared prefix nodes have children after insert [OK]

Common Mistakes:

• Assuming node 'a' has no children
• Confusing node existence with children presence
• Expecting nil or error instead of true

4. Given this Go code snippet for inserting a word into a Trie, what is the bug?

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

medium

A. children map is not initialized before use

B. Loop variable ch should be int, not rune

C. isEnd should be set before loop

D. Function should return a value

Solution

1. Step 1: Check initialization of children map

   The children map must be initialized (e.g., make(map[rune]*TrieNode)) before inserting nodes.

2. Step 2: Identify impact of missing initialization

   Without initialization, accessing children[ch] causes runtime panic (nil map assignment).

3. Final Answer:

   children map is not initialized before use -> Option A

4. Quick Check:

   Uninitialized map causes runtime error [OK]

Hint: Always initialize map before inserting keys [OK]

Common Mistakes:

• Ignoring map initialization
• Misunderstanding rune vs int for keys
• Thinking isEnd needs early assignment

5. You want to insert the words ["go", "gone", "guild"] into a Trie. After insertion, how many children does the root node have, and why?

hard

A. 0, because root has no children

B. 3, because there are three words

C. 2, because 'go' and 'guild' share 'g' but 'gone' differs

D. 1, because all words start with 'g'

Solution

1. Step 1: Analyze first characters of all words

   All words start with the letter 'g', so root node will have one child for 'g'.

2. Step 2: Understand Trie root children count

   Root children count equals distinct first letters of inserted words, here only 'g'.

3. Final Answer:

   1, because all words start with 'g' -> Option D

4. Quick Check:

   Root children = distinct first letters = 1 [OK]

Hint: Root children = unique first letters of words [OK]

Common Mistakes:

• Counting words instead of unique first letters
• Assuming root has no children
• Confusing shared prefixes with root children count