Trie Node Design and Initialization in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie node and what does it typically store?

A Trie node is a building block of a Trie data structure. It typically stores a map or array of child nodes for each possible character and a boolean flag to mark if the node represents the end of a word.

beginner

How do you initialize a Trie node in Go?

In Go, a Trie node can be initialized by creating a struct with a map for children nodes and a boolean for end-of-word. For example: <br> type TrieNode struct { <br> children map[rune]*TrieNode <br> isEnd bool <br> } <br> Then initialize with: <br> node := &TrieNode{children: make(map[rune]*TrieNode)}

intermediate

Why use a map[rune]*TrieNode instead of an array for children in Go Trie nodes?

Using a map[rune]*TrieNode allows flexible storage for any Unicode character keys without wasting space. Arrays are fixed size and waste space if the alphabet is large or sparse.

beginner

What does the isEnd boolean in a Trie node represent?

The isEnd boolean marks whether the current node represents the end of a valid word stored in the Trie. It helps distinguish prefixes from complete words.

beginner

Show a simple Go struct definition for a Trie node with initialization.

type TrieNode struct {<br> children map[rune]*TrieNode<br> isEnd bool<br>}<br><br>func NewTrieNode() *TrieNode {<br> return &TrieNode{children: make(map[rune]*TrieNode)}<br>}

What data type is commonly used to store children nodes in a Go Trie node?

A []int

B map[rune]*TrieNode

C string

D bool

Children nodes are stored in a map with rune keys pointing to TrieNode pointers for flexible character storage.

What does the isEnd field in a Trie node indicate?

A If the node marks the end of a word

B If the node is the root

C If the node is empty

D If the node has children

The isEnd boolean marks the node as the end of a valid word in the Trie.

How do you initialize the children map in a Go Trie node?

A children := nil

B children := []TrieNode{}

C children := make(map[rune]*TrieNode)

D children := 0

The children map must be initialized with make to allocate memory before use.

Why might a map be preferred over an array for children in a Trie node?

A Arrays are dynamic in size

B Arrays are faster for all cases

C Maps cannot store Unicode characters

D Maps use less memory for sparse alphabets

Maps save memory when the alphabet is large but only a few children exist per node.

Which of these is a correct Go struct field for children in a Trie node?

A children map[rune]*TrieNode

B children []int

C children string

D children bool

Children are stored as a map from rune to pointer to TrieNode.

Describe how to design and initialize a Trie node in Go.

Think about what data each node needs to store and how to prepare the map for children.

Explain why a map[rune]*TrieNode is used for children in a Trie node instead of an array.

Consider the size and type of the alphabet and how many children each node might have.