Trie Node Design and Initialization in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Node Initialization

What is the output of this Go code that initializes a Trie node and prints its children count?

DSA Go

package main

import (
	"fmt"
)

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

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode), isEnd: false}
}

func main() {
	node := NewTrieNode()
	fmt.Println(len(node.children))
}

A 0

B 1

C Compilation error

D nil

💡 Hint

Think about what happens when you create a new map in Go and check its length before adding any elements.

The NewTrieNode function creates a TrieNode with an empty map for children. The length of an empty map is 0, so printing len(node.children) outputs 0.

❓ Predict Output

intermediate

Trie Node isEnd Field Default Value

What is the output of this Go code that creates a Trie node and prints the isEnd field?

DSA Go

package main

import (
	"fmt"
)

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

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

func main() {
	node := NewTrieNode()
	fmt.Println(node.isEnd)
}

A 0

B true

C false

D Compilation error

💡 Hint

Boolean fields in Go default to what value if not explicitly set?

In Go, boolean fields default to false if not set. The isEnd field is not set in NewTrieNode, so it prints false.

🔧 Debug

advanced

Identify the Error in Trie Node Initialization

What error does this Go code produce when trying to add a child node to the TrieNode's children map?

DSA Go

package main

import (
	"fmt"
)

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

func main() {
	node := &TrieNode{}
	node.children['a'] = &TrieNode{}
	fmt.Println(len(node.children))
}

A 1

B 0

C Compilation error: invalid map key

D panic: assignment to entry in nil map

💡 Hint

Maps must be initialized before adding keys in Go.

The children map is nil because it was not initialized with make. Assigning to a nil map causes a runtime panic.

❓ Predict Output

advanced

Output After Adding Child to Trie Node

What is the output of this Go code after adding a child node to the TrieNode's children map?

DSA Go

package main

import (
	"fmt"
)

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

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

func main() {
	node := NewTrieNode()
	node.children['b'] = NewTrieNode()
	fmt.Println(len(node.children))
}

A 0

B 1

C Compilation error

D panic: assignment to entry in nil map

💡 Hint

Check if the children map is initialized before adding a child.

The children map is initialized with make, so adding a child increases its length to 1.

🧠 Conceptual

expert

Why Initialize Children Map in Trie Node?

Why is it important to initialize the children map in a TrieNode struct in Go before adding child nodes?

A Because maps in Go are nil by default and assigning to a nil map causes a runtime panic

B Because uninitialized maps automatically create keys with zero values

C Because initializing maps improves performance but is not required

D Because Go requires all struct fields to be initialized explicitly

💡 Hint

Think about what happens when you try to write to a nil map in Go.

Maps in Go default to nil. Writing to a nil map causes a runtime panic. Initializing with make creates a usable map.

Practice

1. What is the primary purpose of a Trie node in a Trie data structure?

easy

A. To store characters and links to child nodes for prefix-based search

B. To store integer values for sorting

C. To hold a single string value only

D. To act as a queue for BFS traversal

Solution

1. Step 1: Understand Trie node role

   A Trie node stores characters and links to child nodes to represent prefixes of words.

2. Step 2: Compare options

   Only To store characters and links to child nodes for prefix-based search correctly describes storing characters and child links for prefix search.

3. Final Answer:

   To store characters and links to child nodes for prefix-based search -> Option A

4. Quick Check:

   Trie node = prefix storage [OK]

Hint: Trie nodes hold characters and children for prefix search [OK]

Common Mistakes:

• Thinking Trie nodes store whole words only
• Confusing Trie nodes with array or queue structures
• Assuming Trie nodes store integer values

2. Which of the following is the correct way to declare a Trie node struct in Go with children for 26 lowercase letters and a boolean to mark end of word?

easy

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

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

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

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

Solution

1. Step 1: Check children type

   Children should be an array of pointers to TrieNode for 26 letters: [26]*TrieNode.

2. Step 2: Check isEnd type

   isEnd should be boolean to mark word end.

3. Final Answer:

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

4. Quick Check:

   Children as pointer array + bool isEnd = type TrieNode struct { children [26]*TrieNode; isEnd bool } [OK]

Hint: Use array of pointers and bool for end marker [OK]

Common Mistakes:

• Using slice instead of fixed array for children
• Using int or string instead of bool for isEnd
• Using map with wrong key type

3. What will be the output of the following Go code snippet?

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

func main() {
  root := &TrieNode{}
  if root.children[0] == nil {
    println("No child at index 0")
  } else {
    println("Child exists at index 0")
  }
}

medium

A. Compilation error

B. No child at index 0

C. Child exists at index 0

D. Runtime panic

Solution

1. Step 1: Understand initialization of children array

   When root is created, children array elements are nil pointers by default.

2. Step 2: Check condition in if statement

   root.children[0] is nil, so condition is true and prints "No child at index 0".

3. Final Answer:

   No child at index 0 -> Option B

4. Quick Check:

   Uninitialized children = nil pointers [OK]

Hint: Uninitialized pointer arrays have nil elements [OK]

Common Mistakes:

• Assuming children are auto-initialized with nodes
• Expecting compilation or runtime errors
• Confusing zero values for pointers

4. Identify the error in this Go code snippet for initializing a Trie node:

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

func NewNode() *TrieNode {
  node := TrieNode{}
  node.isEnd = false
  return &node
}

medium

A. isEnd should be true by default

B. Children array is not initialized with pointers

C. Function returns a pointer to a local variable

D. Syntax error in struct declaration

Solution

1. Step 1: Analyze the NewNode function

   The function creates a local struct variable node and returns its address &node.

2. Step 2: Identify the problem

   Returning the pointer to a local variable risks a dangling pointer after the function exits, even though Go's escape analysis heap-allocates it; it's poor practice and should use &TrieNode{} instead.

3. Final Answer:

   Function returns a pointer to a local variable -> Option C

4. Quick Check:

   Return &local_var = bad practice [OK]

Hint: Avoid returning pointers to local variables [OK]

Common Mistakes:

• Thinking children must be explicitly initialized
• Confusing pointer nil with error
• Assuming isEnd default must be true

5. You want to initialize a Trie node in Go that supports Unicode characters instead of just 26 lowercase letters. Which data structure change is best to support this efficiently?

hard

A. Keep children as [26]*TrieNode but convert Unicode to lowercase ASCII

B. Increase children array size to 65536 elements

C. Use slice []*TrieNode with fixed size 26

D. Change children from [26]*TrieNode array to map[rune]*TrieNode

Solution

1. Step 1: Understand Unicode support needs

   Unicode has many characters beyond 26 letters, so fixed array is inefficient.

2. Step 2: Evaluate data structure options

   Using map[rune]*TrieNode allows dynamic keys for any Unicode character efficiently.

3. Step 3: Reject other options

   Array of 65536 is large and wasteful; slice with fixed size 26 is too small; converting Unicode to ASCII loses data.

4. Final Answer:

   Change children from [26]*TrieNode array to map[rune]*TrieNode -> Option D

5. Quick Check:

   Map with rune keys = Unicode support [OK]

Hint: Use map with rune keys for Unicode children [OK]

Common Mistakes:

• Using large fixed arrays wasting memory
• Ignoring Unicode complexity
• Trying to fit Unicode into ASCII-only arrays