Trie Node Design and Initialization in DSA Go

Mental Model

A trie node holds links to child nodes for each letter and a marker if a word ends here.

Analogy: Think of a trie node like a mailbox with 26 slots for letters a to z, and a flag to say if a word stops at this mailbox.

root
 ↓
[ ] -> [ ] -> [ ] -> ... -> [ ]
Each [ ] is a child slot for a letter, initially empty (nil).

Dry Run Walkthrough

Input: Create a trie node for English lowercase letters with no words inserted yet.

Goal: Initialize a trie node with empty child links and end-of-word marker set to false.

Step 1: Create a new trie node instance

Node: children = [nil, nil, ..., nil] (26 slots), isEnd = false

Why: We need a clean node with no children and no word ending yet

Result:

Node: children = [nil, nil, ..., nil] (26 slots), isEnd = false

Annotated Code

DSA Go

package main

import "fmt"

// TrieNode represents one node in the trie
// It has 26 children for each lowercase English letter
// and a boolean to mark if a word ends here

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

// NewTrieNode creates and returns a new empty trie node
func NewTrieNode() *TrieNode {
	return &TrieNode{
		children: [26]*TrieNode{}, // all nil initially
		isEnd: false,              // no word ends here yet
	}
}

func main() {
	node := NewTrieNode()
	fmt.Printf("Children slots: %d, isEnd: %v\n", len(node.children), node.isEnd)
}

return &TrieNode{children: [26]*TrieNode{}, isEnd: false}

initialize all child pointers to nil and isEnd to false

Output

Children slots: 26, isEnd: false

Complexity Analysis

Time: O(1) because initialization just sets fixed size array and a boolean

Space: O(1) for one node with fixed 26 children slots and one boolean

vs Alternative: Compared to dynamic maps, fixed array uses more space but faster access by index

Edge Cases

No children nodes yet

All children pointers are nil, no word ends here

DSA Go

return &TrieNode{children: [26]*TrieNode{}, isEnd: false}

When to Use This Pattern

When you need to store many words sharing prefixes, use a trie node with fixed children array and end marker to build the trie efficiently.

Common Mistakes

Mistake: Using a slice or map for children without fixed size causes slower access or more complexity
Fix: Use a fixed size array of 26 pointers for constant time access by letter index

Summary

It creates a trie node with 26 empty child slots and a flag to mark word end.

Use it when building a trie to store words by their letters efficiently.

The key is fixed size children array for each letter and a boolean to mark word completion.