How to Implement a Trie in Go

Implement a Trie in Go by defining a TrieNode struct with a map of children and a boolean flag for word endings, then creating Insert and Search methods to traverse the tree.

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

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

func (root *TrieNode) Insert(word string) {
	node := root
	for _, char := range word {
		if _, ok := node.children[char]; !ok {
			node.children[char] = NewTrieNode()
		}
		node = node.children[char]
	}
	node.isEnd = true
}

func (root *TrieNode) Search(word string) bool {
	node := root
	for _, char := range word {
		if child, ok := node.children[char]; ok {
			node = child
		} else {
			return false
		}
	}
	return node.isEnd
}

A Trie is a tree-like data structure that stores strings efficiently by sharing common prefixes. It matters because it allows you to search for words or prefixes much faster than scanning a list, similar to how you use a dictionary to find a word by its starting letters.