Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Go - Why This Pattern

Mental Model

A trie stores strings by sharing common beginnings, making it fast to find words with the same prefix. Hash maps store whole words separately, missing this shared structure.

Analogy: Imagine a tree of roads where each road letter leads to the next letter in a word. Many words share the same first roads, so you only build those roads once. A hash map is like separate houses with no shared roads, so you must check each house fully.

root
 ↓
 c -> a -> t -> [end]
      ↓
      r -> [end]
 d -> o -> g -> [end]

Dry Run Walkthrough

Input: Insert words: "cat", "car", "dog" into trie and hash map

Goal: Show how trie shares prefixes and hash map stores full words separately

Step 1: Insert 'cat' into trie

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

Why: We create nodes for each letter since trie is empty

Step 2: Insert 'car' into trie

root -> c -> a -> t -> [end]
               ↓
               r -> [end]

Why: We reuse 'c' and 'a' nodes, add new node 'r' for different ending

Step 3: Insert 'dog' into trie

root -> c -> a -> t -> [end]
               ↓
               r -> [end]
  ↓
  d -> o -> g -> [end]

Why: Add new branch for 'dog' starting with 'd' since no common prefix

Step 4: Store words in hash map

"cat" -> value
"car" -> value
"dog" -> value

Why: Hash map stores each word as a separate key with no shared parts

Result:

Trie shares prefix nodes for 'c' and 'a' saving space and enabling prefix search.
Hash map stores full words separately with no prefix sharing.

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 curr.children[ch] == nil {
			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 trie (helper for visualization)
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() {
	words := []string{"cat", "car", "dog"}

	// Using Trie
	trie := NewTrie()
	for _, w := range words {
		trie.Insert(w) // insert each word
	}
	fmt.Println("Words in Trie:")
	trie.PrintTrie()

	// Using Hash Map
	hashMap := make(map[string]bool)
	for _, w := range words {
		hashMap[w] = true // store full word
	}
	fmt.Println("Words in Hash Map:")
	for k := range hashMap {
		fmt.Println(k)
	}
}

if curr.children[ch] == nil { curr.children[ch] = NewTrieNode() // create node if missing }

create new node only if letter path does not exist to share prefixes

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

advance current pointer to next letter node

curr.isEnd = true // mark end of word

mark node as end of a valid word

hashMap[w] = true // store full word

store entire word as key in hash map without sharing

Output

Words in Trie:

car

cat

dog

Words in Hash Map:

cat

car

dog

Complexity Analysis

Time: O(m) per insert where m is word length because we process each letter once

Space: O(n*m) in worst case for n words of length m, but shared prefixes reduce space

vs Alternative: Hash map stores full words separately using O(n*m) space with no prefix sharing, making prefix queries inefficient

Edge Cases

Empty string insertion

Trie marks root as end of word; hash map stores empty string key

DSA Go

curr.isEnd = true // mark end of word

Words with shared prefixes

Trie shares nodes for common prefix letters, saving space

DSA Go

if curr.children[ch] == nil { curr.children[ch] = NewTrieNode() }

Words with no common prefix

Trie creates separate branches for each word

DSA Go

if curr.children[ch] == nil { curr.children[ch] = NewTrieNode() }

When to Use This Pattern

When you need fast prefix search or autocomplete on strings, reach for trie because hash maps cannot efficiently share prefixes or support prefix queries.

Common Mistakes

Mistake: Creating new nodes for every letter without checking if node exists
Fix: Check if child node exists before creating to share prefixes

Mistake: Not marking the end of word node
Fix: Set isEnd = true at last letter node to mark complete word

Summary

Trie stores strings by sharing common prefixes for efficient prefix search.

Use trie when you want to find or autocomplete words by their beginnings quickly.

The key insight is that tries save space and time by reusing nodes for shared prefixes, unlike hash maps.