How to create a trie in Go

Overview

Trie is a tree data structure usually used for efficient data retrieval. In trie, a single letter of a word for each node is preserved. The nodes of a given word are connected in an organized way from the root to the last letter of the word. To find any word in the node, the trie fetches that letter through the prefix of that particular word.

Let's explore an illustration for better visualization:

package main
import "fmt"
//Declaring trie_Node  for creating node in a trie 
type trie_Node struct {
//assigning limit of 26 for child nodes
    childrens [26]*trie_Node
//declaring a bool variable to check the word end.    
    wordEnds bool
}
//Initializing the root of the trie
type trie struct {
    root *trie_Node
}
//inititlaizing a new trie 
func trieData() *trie {
    t := new(trie)
    t.root = new(trie_Node)
    return t
    }
//Passing words to trie
func (t *trie) insert(word string) {
    current := t.root
    for _, wr := range word {
        index := wr - 'a'
        if current.childrens[index] == nil {
            current.childrens[index] = new(trie_Node)
        }
        current = current.childrens[index]
    }
    current.wordEnds = true
}
//Initializing the search for word in node
func (t *trie) search(word string) int {
    current := t.root
    for _, wr := range word {
        index := wr - 'a'
        if current.childrens[index] == nil {
            return 0
        }
        current = current.childrens[index]
    }
    if current.wordEnds {
        return 1
    }
    return 0
}
//initializing the main function
func main() {
    trie := trieData()
//Passing the words in the trie
    word := []string{"aqua", "jack", "card", "care"}
    for _, wr := range word  {
        trie.insert(wr)
    }
//initializing search for the words    
    words_Search := []string{"aqua", "jack", "card", "care","cat", "dog","can"}
    for  _, wr := range words_Search {
        found := trie.search(wr)
        if found == 1 {
            fmt.Printf("\"%s\"Word found in trie\n", wr)
        } else {
            fmt.Printf(" \"%s\" Word not found in trie\n", wr)
        }
    }
}

Explanation

Lines 4–9: We initialize the node in a trie and limit the child nodes, childrens [26]*trie_Node, to 26.
Lines 11–12: We initialize the pointer on the root node of the trie by using root *trie_Node.
Lines 15–19: We initialize a new trie by t := new(trie) for a new word to store in it.
Lines 21–31: We declare the func (t *trie)insert(word string) function to pass the values in the trie. We use a for loop in the program to pass each letter of the word to the node.
Lines 33–46: We initialize the function to search the words in a trie. We use the for loop to fetch the word letter node by node. We add a condition in the if condition specifying that if we found a letter in the node, we move to the next trie.
Lines 48–65: We call the trieData function to insert a word to the trie's nodes. After this, we initialize an array, word_Search. In this array, we pass the words we want to search. In the end, we use the if condition to check whether or not we found the word in it.

How to create a trie in Go

Overview

Example

Explanation