Trie for Prefix Lookup in Go

package main

import (
	"fmt"
	"sort"
	"strings"
)

type node struct {
	children map[rune]*node
	terminal bool
}

type Trie struct {
	root *node
	size int
}

func NewTrie() *Trie {
	return &Trie{root: &node{children: make(map[rune]*node)}}
}

func (t *Trie) Insert(word string) bool {
	word = strings.TrimSpace(word)
	if word == "" {
		return false
	}
	current := t.root
	for _, char := range word {
		next, ok := current.children[char]
		if !ok {
			next = &node{children: make(map[rune]*node)}
			current.children[char] = next
		}
		current = next
	}
	if current.terminal {
		return false
	}
	current.terminal = true
	t.size++
	return true
}

func (t *Trie) HasPrefix(prefix string) bool {
	return t.find(prefix) != nil
}

func (t *Trie) find(prefix string) *node {
	current := t.root
	for _, char := range prefix {
		next, ok := current.children[char]
		if !ok {
			return nil
		}
		current = next
	}
	return current
}

func (t *Trie) Complete(prefix string, limit int) []string {
	if limit < 1 {
		return nil
	}
	start := t.find(prefix)
	if start == nil {
		return nil
	}
	var found []string
	walk(start, prefix, &found)
	sort.Strings(found)
	if len(found) > limit {
		found = found[:limit]
	}
	return found
}

func walk(current *node, prefix string, found *[]string) {
	if current.terminal {
		*found = append(*found, prefix)
	}
	chars := make([]rune, 0, len(current.children))
	for char := range current.children {
		chars = append(chars, char)
	}
	sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
	for _, char := range chars {
		walk(current.children[char], prefix+string(char), found)
	}
}

func main() {
	trie := NewTrie()
	for _, word := range []string{"gopher", "go", "golang", "rust", "ruby"} {
		trie.Insert(word)
	}
	fmt.Println("has prefix go:", trie.HasPrefix("go"))
	fmt.Println("has prefix zig:", trie.HasPrefix("zig"))
	fmt.Println(trie.Complete("go", 3))
}