Trie Insert Operation in DSA Go

Mental Model

A trie stores words by branching letters step-by-step, sharing common prefixes to save space.

Analogy: Imagine a tree where each branch is a letter, and words grow by adding branches only when needed, like building a family tree of words.

root
 ↓
[ ]
Each node points to next letters, starting empty at root.

Dry Run Walkthrough

Input: Insert words: "cat", then "car" into an empty trie

Goal: Build a trie that stores both words sharing the prefix 'ca'

Step 1: Insert 'c' from 'cat' at root

root -> c -> [ ]

Why: Start the first branch for the letter 'c'

Step 2: Insert 'a' after 'c'

root -> c -> a -> [ ]

Why: Add next letter 'a' continuing the word

Step 3: Insert 't' after 'a' and mark end of word

root -> c -> a -> t* -> [ ]

Why: Complete the word 'cat' by marking 't' as word end

Step 4: Insert 'c' from 'car' starting at root (exists)

root -> c -> a -> t* -> [ ]

Why: Reuse existing 'c' node for shared prefix

Step 5: Insert 'a' after 'c' (exists)

root -> c -> a -> t* -> [ ]

Why: Reuse existing 'a' node for shared prefix

Step 6: Insert 'r' after 'a' and mark end of word

root -> c -> a -> t* -> r* -> [ ]

Why: Add new branch 'r' to complete 'car'

Result:

root -> c -> a -> t* -> r* -> [ ]
* marks end of word

Annotated Code

DSA Go

package main

import "fmt"

// TrieNode represents each node in the trie
type TrieNode struct {
	children map[rune]*TrieNode
	isEnd bool
}

// Trie structure with root node
type Trie struct {
	root *TrieNode
}

// NewTrieNode creates a new trie node
func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

// NewTrie creates a new trie
func NewTrie() *Trie {
	return &Trie{root: NewTrieNode()}
}

// Insert adds a word to the trie
func (t *Trie) Insert(word string) {
	curr := t.root
	for _, ch := range word {
		if _, exists := curr.children[ch]; !exists {
			curr.children[ch] = NewTrieNode() // create node if missing
		}
		curr = curr.children[ch] // move to next node
	}
	curr.isEnd = true // mark end of word
}

// PrintTrie prints all words in the trie
func (t *Trie) PrintTrie() {
	var dfs func(node *TrieNode, prefix string)
	dfs = func(node *TrieNode, prefix string) {
		if node.isEnd {
			fmt.Println(prefix)
		}
		for ch, child := range node.children {
			dfs(child, prefix+string(ch))
		}
	}
	dfs(t.root, "")
}

func main() {
	trie := NewTrie()
	trie.Insert("cat")
	trie.Insert("car")
	trie.PrintTrie()
}

if _, exists := curr.children[ch]; !exists { curr.children[ch] = NewTrieNode() // create node if missing }

create new node only if letter branch does not exist

curr = curr.children[ch] // move to next node

advance current pointer to next letter node

curr.isEnd = true // mark end of word

mark current node as end of inserted word

Output

car

cat

Complexity Analysis

Time: O(m) because we process each of the m letters in the word once

Space: O(m) in worst case when all letters are new and need new nodes

vs Alternative: Compared to storing words in a list, trie insert is faster for prefix queries but uses more space for nodes

Edge Cases

Insert empty string

Marks root as end of word, representing empty word

DSA Go

curr.isEnd = true // mark end of word

Insert word that is prefix of existing word (e.g., insert 'ca' after 'cat')

Marks existing node as end of word without adding nodes

DSA Go

curr.isEnd = true // mark end of word

Insert duplicate word

No new nodes created, just marks end again

DSA Go

if _, exists := curr.children[ch]; !exists { ... }

When to Use This Pattern

When you need to store many words sharing prefixes efficiently, use a trie insert pattern to build a prefix tree.

Common Mistakes

Mistake: Creating new nodes for letters that already exist, causing duplicate branches
Fix: Check if child node exists before creating a new one

Mistake: Not marking the end of word, so words are not recognized as complete
Fix: Set isEnd = true at the last node of the inserted word

Summary

Inserts words letter by letter into a tree structure sharing prefixes.

Use when storing many words to quickly check prefixes or existence.

The key is to reuse existing letter nodes and mark word ends properly.