Master Trie (Prefix Tree) in Go: Insertion, Search, Deletion & Unit Tests

Introduction

Trie (prefix tree) is a multi‑branch tree for efficient string insertion, deletion, and lookup. Commonly used in autocomplete, spell checking, and IP routing.

Basic Structure

Each node stores a character; the path from the root to a node forms a prefix. Edges correspond to characters, and a boolean flag marks the end of a word.

Example

(root)
       /    \
      c      b
     / \    / \
    a   a  a   a
   /    \ /   / \
  t      p   t   r

Operations

Insertion

Walk the tree character by character, creating missing nodes.

Go implementation

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

type Trie struct {
    root *TrieNode
}

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

func (t *Trie) Insert(word string) {
    node := t.root
    for _, char := range word {
        if _, found := node.children[char]; !found {
            node.children[char] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[char]
    }
    node.isEnd = true
}

Search

Verify each character exists and that the final node is marked as a word end.

Go implementation

func (t *Trie) Search(word string) bool {
    node := t.root
    for _, char := range word {
        if _, found := node.children[char]; !found {
            return false
        }
        node = node.children[char]
    }
    return node.isEnd
}

Deletion

Recursively remove nodes that are no longer needed after unmarking the word end.

Go implementation

func (t *Trie) Delete(word string) bool {
    return t.deleteHelper(t.root, word, 0)
}

func (t *Trie) deleteHelper(node *TrieNode, word string, depth int) bool {
    if node == nil {
        return false
    }
    if depth == len(word) {
        if !node.isEnd {
            return false
        }
        node.isEnd = false
        return len(node.children) == 0
    }
    char := rune(word[depth])
    if t.deleteHelper(node.children[char], word, depth+1) {
        delete(node.children, char)
        return !node.isEnd && len(node.children) == 0
    }
    return false
}

Applications

Autocomplete – suggest completions for a typed prefix.

Spell checking – verify word existence in a dictionary.

IP routing – store and lookup IP address prefixes efficiently.

Complete Go Code

package trie

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

type Trie struct {
    root *TrieNode
}

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

func (t *Trie) Insert(word string) {
    node := t.root
    for _, char := range word {
        if _, found := node.children[char]; !found {
            node.children[char] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[char]
    }
    node.isEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.root
    for _, char := range word {
        if _, found := node.children[char]; !found {
            return false
        }
        node = node.children[char]
    }
    return node.isEnd
}

func (t *Trie) Delete(word string) bool {
    return t.deleteHelper(t.root, word, 0)
}

func (t *Trie) deleteHelper(node *TrieNode, word string, depth int) bool {
    if node == nil {
        return false
    }
    if depth == len(word) {
        if !node.isEnd {
            return false
        }
        node.isEnd = false
        return len(node.children) == 0
    }
    char := rune(word[depth])
    if t.deleteHelper(node.children[char], word, depth+1) {
        delete(node.children, char)
        return !node.isEnd && len(node.children) == 0
    }
    return false
}

Unit Tests

package trie

import "testing"

func TestTrie_Insert(t *testing.T) {
    trie := NewTrie()
    trie.Insert("apple")
    trie.Insert("app")
    trie.Insert("banana")
    trie.Insert("bat")
    if !trie.Search("apple") { t.Errorf("Expected 'apple' to be found") }
    if !trie.Search("app") { t.Errorf("Expected 'app' to be found") }
    if !trie.Search("banana") { t.Errorf("Expected 'banana' to be found") }
    if !trie.Search("bat") { t.Errorf("Expected 'bat' to be found") }
    if trie.Search("orange") { t.Errorf("Expected 'orange' to not be found") }
    if trie.Search("appl") { t.Errorf("Expected 'appl' to not be found") }
    if trie.Search("b") { t.Errorf("Expected 'b' to not be found") }
    // Additional test cases omitted for brevity
}

Conclusion

Trie provides an efficient way to handle string‑based problems; mastering its core operations and typical use‑cases can improve performance in many software projects.