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.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing many strings?

easy

A. Because Trie can efficiently find all strings with a common prefix

B. Because Hash Map uses less memory than Trie

C. Because Trie stores strings as keys directly without nodes

D. Because Hash Map automatically sorts strings alphabetically

Solution

1. Step 1: Understand Trie prefix search

   Trie stores strings in a tree form where each node represents a character, allowing quick prefix searches.

2. Step 2: Compare with Hash Map capabilities

   Hash Map stores full strings as keys but cannot efficiently find all strings sharing a prefix without checking all keys.

3. Final Answer:

   Because Trie can efficiently find all strings with a common prefix -> Option A

4. Quick Check:

   Trie = Efficient prefix search [OK]

Hint: Trie excels at prefix search, Hash Map does not [OK]

Common Mistakes:

• Thinking Hash Map sorts keys automatically
• Believing Trie uses less memory always
• Confusing Trie nodes with full string keys

2. Which of the following is the correct way to declare a Trie node struct in Go?

easy

A. type TrieNode struct { children map[string]int; isEnd int }

B. type TrieNode struct { children []int; isEnd string }

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

D. type TrieNode struct { children map[int]string; isEnd bool }

Solution

1. Step 1: Identify correct children type for TrieNode

   Children should map characters (rune) to child nodes (pointer to TrieNode).

2. Step 2: Check isEnd field type

   isEnd should be a boolean indicating if node marks end of a word.

3. Final Answer:

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } -> Option C

4. Quick Check:

   Children map[rune]*TrieNode and isEnd bool [OK]

Hint: Children map keys are runes, isEnd is bool [OK]

Common Mistakes:

• Using wrong map key or value types
• Setting isEnd as string or int instead of bool
• Using slice instead of map for children

3. What will be the output of the following Go code snippet?

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

func main() {
  root := &TrieNode{children: make(map[rune]*TrieNode)}
  word := "cat"
  node := root
  for _, ch := range word {
    if node.children[ch] == nil {
      node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
    }
    node = node.children[ch]
  }
  node.isEnd = true
  
  // Check if 'car' is in Trie
  node = root
  checkWord := "car"
  found := true
  for _, ch := range checkWord {
    if node.children[ch] == nil {
      found = false
      break
    }
    node = node.children[ch]
  }
  if found && node.isEnd {
    println("Found")
  } else {
    println("Not Found")
  }
}

medium

A. Found

B. Not Found

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Insert 'cat' into Trie

   The code adds nodes for 'c', 'a', 't' and marks 't' node as end of word.

2. Step 2: Search for 'car' in Trie

   Traversal finds 'c' and 'a' nodes but no child for 'r', so found becomes false.

3. Final Answer:

   Not Found -> Option B

4. Quick Check:

   Only 'cat' inserted, 'car' missing last node [OK]

Hint: Check each character node; missing means Not Found [OK]

Common Mistakes:

• Assuming partial prefix means found
• Confusing isEnd flag usage
• Expecting runtime errors from nil map access

4. The following Go code tries to insert a word into a Trie but causes a runtime panic. What is the error?

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

func insert(root *TrieNode, word string) {
  node := root
  for _, ch := range word {
    if node.children[ch] == nil {
      node.children[ch] = &TrieNode{}
    }
    node = node.children[ch]
  }
  node.isEnd = true
}

func main() {
  root := &TrieNode{}
  insert(root, "dog")
}

medium

A. children map is not initialized before use

B. isEnd should be an int, not bool

C. Function insert missing return type

D. root pointer is nil

Solution

1. Step 1: Check initialization of children map

   Root node's children map is nil because it was not created with make(), causing panic on access.

2. Step 2: Understand panic cause

   Accessing or assigning to nil map causes runtime panic in Go.

3. Final Answer:

   children map is not initialized before use -> Option A

4. Quick Check:

   Nil map access causes panic [OK]

Hint: Always initialize maps with make() before use [OK]

Common Mistakes:

• Ignoring map initialization
• Thinking isEnd type causes panic
• Assuming nil pointer for root

5. You want to find all words in a large dictionary that start with the prefix "pre". Why is a Trie better than a Hash Map for this task, and how would you implement the search?

hard

A. Trie uses hashing internally to speed up prefix search

B. Hash Map sorts keys internally, so prefix search is a simple range query

C. Hash Map stores words as linked lists, making prefix search faster

D. Trie stores words by prefix nodes, allowing direct traversal to prefix end; then collect all descendant words

Solution

1. Step 1: Understand Trie prefix traversal

   In Trie, each character is a node; to find prefix "pre", traverse nodes 'p' -> 'r' -> 'e'.

2. Step 2: Collect all words under prefix node

   From the 'e' node, recursively collect all words by exploring child nodes marking word ends.

3. Final Answer:

   Trie stores words by prefix nodes, allowing direct traversal to prefix end; then collect all descendant words -> Option D

4. Quick Check:

   Trie = Direct prefix traversal + collect descendants [OK]

Hint: Traverse prefix nodes, then gather all child words [OK]

Common Mistakes:

• Assuming Hash Map sorts keys automatically
• Thinking Trie uses hashing internally
• Confusing linked list with Hash Map storage