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:

Trie

Example

In the illustration above, we have a trie in which four words are stored. These words are aqua, care, card, and jack. All word letters stored in each node are connected with the letter node of that particular word. When we search that particular word, it retrieves that word by retrieving the letter node of each word, one by one.

Let’s explore a programming example:

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.
Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
You TubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved