Trie (Prefix Tree) Implementation in Go

A Trie (pronounced “try”), also known as a prefix tree, is a tree-like data structure used to store a dynamic set of strings where the keys are usually strings. It is particularly useful for searching strings with shared prefixes, making it an excellent choice for applications like autocomplete, spell checking, and IP routing.

Program Structure

The Go program implementing the Trie (Prefix Tree) is structured into the following components:

1. TrieNode Struct: This struct represents a node in the Trie, containing a map of child nodes and a boolean indicating if the node marks the end of a word.
2. Trie Struct: This struct represents the Trie itself, containing the root node.
3. Insert Method: This method inserts a word into the Trie.
4. Search Method: This method checks if a word exists in the Trie.
5. StartsWith Method: This method checks if any word in the Trie starts with a given prefix.

Go Code Implementation

package main

import "fmt"

// TrieNode represents a node in the Trie
type TrieNode struct {
    children map[rune]*TrieNode // Map of child nodes
    isEnd    bool               // Is true if the node represents the end of a word
}

// Trie represents the Trie structure
type Trie struct {
    root *TrieNode // Root node of the Trie
}

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

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

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

// StartsWith checks if there is any word in the Trie that starts with the given prefix
func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for _, char := range prefix {
        if _, exists := node.children[char]; !exists {
            return false
        }
        node = node.children[char]
    }
    return true
}

func main() {
    // Create a new Trie and insert some words
    trie := NewTrie()
    words := []string{"apple", "app", "apricot", "banana", "band", "bandana", "bandit"}
    for _, word := range words {
        trie.Insert(word)
    }

    // Test the search function
    fmt.Println("Search 'apple':", trie.Search("apple"))   // Output: true
    fmt.Println("Search 'app':", trie.Search("app"))       // Output: true
    fmt.Println("Search 'appl':", trie.Search("appl"))     // Output: false
    fmt.Println("Search 'banana':", trie.Search("banana")) // Output: true
    fmt.Println("Search 'bandit':", trie.Search("bandit")) // Output: true
    fmt.Println("Search 'bandana':", trie.Search("bandana")) // Output: true

    // Test the startsWith function
    fmt.Println("StartsWith 'ban':", trie.StartsWith("ban")) // Output: true
    fmt.Println("StartsWith 'appl':", trie.StartsWith("appl")) // Output: true
    fmt.Println("StartsWith 'bat':", trie.StartsWith("bat"))   // Output: false
}
    

Explanation of the Code

Here’s a breakdown of the code:

• TrieNode Struct: The TrieNode struct represents each node in the Trie. It contains a map of child nodes, where each key is a character, and a boolean isEnd that indicates if the node represents the end of a word.
• Trie Struct: The Trie struct represents the Trie itself and contains the root node.
• Insert Method: This method inserts a word into the Trie by iterating over each character in the word and creating the necessary child nodes if they don’t already exist. The last node corresponding to the last character in the word is marked as the end of a word by setting isEnd to true.
• Search Method: This method checks if a word exists in the Trie by traversing the Trie nodes corresponding to each character in the word. If the traversal reaches the end of the word and the isEnd flag is set to true, the word exists in the Trie.
• StartsWith Method: This method checks if there is any word in the Trie that starts with the given prefix. It returns true if the Trie contains the prefix, otherwise false.

Usage Example

Here’s an example of how you might use this Trie implementation in a Go program:

func main() {
    // Create a new Trie and insert some words
    trie := NewTrie()
    words := []string{"apple", "app", "apricot", "banana", "band", "bandana", "bandit"}
    for _, word := range words {
        trie.Insert(word)
    }

    // Test the search function
    fmt.Println("Search 'apple':", trie.Search("apple"))   // Output: true
    fmt.Println("Search 'app':", trie.Search("app"))       // Output: true
    fmt.Println("Search 'appl':", trie.Search("appl"))     // Output: false
    fmt.Println("Search 'banana':", trie.Search("banana")) // Output: true
    fmt.Println("Search 'bandit':", trie.Search("bandit")) // Output: true
    fmt.Println("Search 'bandana':", trie.Search("bandana")) // Output: true

    // Test the startsWith function
    fmt.Println("StartsWith 'ban':", trie.StartsWith("ban")) // Output: true
    fmt.Println("StartsWith 'appl':", trie.StartsWith("appl")) // Output: true
    fmt.Println("StartsWith 'bat':", trie.StartsWith("bat"))   // Output: false
}
    

Conclusion

This Go program demonstrates a basic implementation of a Trie (Prefix Tree), a powerful data structure that is highly efficient for operations involving prefix-based searches. The Trie is ideal for applications like autocomplete, spell checking, and other scenarios where fast retrieval of words or prefixes is required.