Trie Insert Operation in DSA Go - Build from Scratch

Trie Insert Operation

📖 Scenario: You are building a simple word dictionary to quickly check if words exist. You will create a Trie data structure to store words efficiently.

🎯 Goal: Build a Trie and insert words into it step-by-step. Finally, print the Trie's root children keys to see the first letters stored.

📋 What You'll Learn

Create a TrieNode struct with a map for children and a boolean for end of word

Create a Trie struct with a root TrieNode

Add a method Insert(word string) to add words to the Trie

Insert given words and print the root children keys

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and IP routing to quickly find words or prefixes.

💼 Career

Understanding Trie insertions is important for roles involving search engines, text processing, and efficient data retrieval.

1

Create TrieNode and Trie structs

Create a struct called TrieNode with a field children of type map[rune]*TrieNode and a field isEnd of type bool. Then create a struct called Trie with a field root of type *TrieNode. Finally, create a function NewTrieNode() that returns a pointer to a new TrieNode with children initialized as an empty map and isEnd set to false.

DSA Go

# Your code here

Hint

Define the structs and initialize the children map in NewTrieNode.

2

Initialize Trie with root node

Create a function NewTrie() that returns a pointer to a new Trie with its root initialized by calling NewTrieNode().

DSA Go

package main

import "fmt"

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

type Trie struct {
    root *TrieNode
}

func NewTrieNode() *TrieNode {
    return &TrieNode{children: make(map[rune]*TrieNode), isEnd: false}
}

// Your code here

func main() {
    // Step 1 code only
}

Hint

Create NewTrie to initialize the root node of the Trie.

3

Add Insert method to Trie

Add a method Insert(word string) to the Trie struct. This method should start from the root node and for each character in word, check if it exists in the current node's children. If not, create a new TrieNode and add it to children. Move to the child node and after the last character, mark isEnd as true.

DSA Go

package main

import "fmt"

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

type Trie struct {
    root *TrieNode
}

func NewTrieNode() *TrieNode {
    return &TrieNode{children: make(map[rune]*TrieNode), isEnd: false}
}

func NewTrie() *Trie {
    return &Trie{root: NewTrieNode()}
}

// Add Insert method to Trie
// Your code here

func main() {
    // Step 2 code only
}

Hint

Loop over each character, create nodes if missing, and mark the end of the word.

4

Insert words and print root children keys

In main(), create a new Trie by calling NewTrie(). Insert the words "go", "golang", and "git" using the Insert method. Then print the keys of the root node's children map as a slice of runes.

DSA Go

package main

import "fmt"

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

type Trie struct {
    root *TrieNode
}

func NewTrieNode() *TrieNode {
    return &TrieNode{children: make(map[rune]*TrieNode), isEnd: false}
}

func NewTrie() *Trie {
    return &Trie{root: NewTrieNode()}
}

func (t *Trie) Insert(word string) {
    current := t.root
    for _, ch := range word {
        if _, ok := current.children[ch]; !ok {
            current.children[ch] = NewTrieNode()
        }
        current = current.children[ch]
    }
    current.isEnd = true
}

func main() {
    // Insert words and print root children keys
    // Your code here
}

Hint

Insert the words and print the root children keys. The output should be a slice with the rune for 'g' (103).