Autocomplete System with Trie in DSA Go

Mental Model

A trie stores words by sharing common prefixes, so we can quickly find all words starting with a given prefix.

Analogy: Imagine a tree of roads where each road sign is a letter. To find all places starting with 'ca', you follow the roads 'c' then 'a' and see all destinations branching from there.

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

Dry Run Walkthrough

Input: words: ["cat", "car", "cars", "dog"], prefix: "ca"

Goal: Find all words starting with prefix "ca"

Step 1: Insert word "cat" into trie

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

Why: Add each letter as a node, mark end of word at 't'

Step 2: Insert word "car" into trie

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

Why: Share prefix 'ca', add 'r' node and mark end

Step 3: Insert word "cars" into trie

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

Why: Extend from 'r' node with 's' and mark end

Step 4: Insert word "dog" into trie

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

Why: Add new branch for 'dog'

Step 5: Search prefix "ca" in trie

At node 'a' after root -> c -> a

Why: Traverse prefix letters to reach node where words start

Step 6: Collect all words starting from node 'a'

Found words: "cat", "car", "cars"

Why: Gather all words by exploring all branches from prefix node

Result:

root -> c -> a -> t [end]
               ↓
               r -> s [end]
 d -> o -> g [end]
Autocomplete results for "ca": ["cat", "car", "cars"]

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 child node
	}
	curr.isEnd = true // mark end of word
}

// searchNode finds the node matching prefix
func (t *Trie) searchNode(prefix string) *TrieNode {
	curr := t.root
	for _, ch := range prefix {
		if curr.children[ch] == nil {
			return nil // prefix not found
		}
		curr = curr.children[ch] // move to next node
	}
	return curr
}

// collectWords recursively collects all words from node
func (t *Trie) collectWords(node *TrieNode, prefix string, results *[]string) {
	if node.isEnd {
		*results = append(*results, prefix) // found a word
	}
	for ch, child := range node.children {
		t.collectWords(child, prefix+string(ch), results) // explore children
	}
}

// Autocomplete returns all words starting with prefix
func (t *Trie) Autocomplete(prefix string) []string {
	results := []string{}
	node := t.searchNode(prefix) // find prefix node
	if node == nil {
		return results // no words found
	}
	t.collectWords(node, prefix, &results) // collect all words
	return results
}

func main() {
	trie := NewTrie()
	words := []string{"cat", "car", "cars", "dog"}
	for _, w := range words {
		trie.Insert(w) // insert each word
	}
	prefix := "ca"
	results := trie.Autocomplete(prefix) // get autocomplete
	fmt.Printf("Autocomplete results for \"%s\": %v\n", prefix, results)
}

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

create new node if letter path does not exist

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

advance current node to next letter node

curr.isEnd = true // mark end of word

mark node as end of a valid word

if curr.children[ch] == nil { return nil // prefix not found }

stop search if prefix letter missing

if node.isEnd { *results = append(*results, prefix) // found a word }

add word to results when end node reached

t.collectWords(child, prefix+string(ch), results) // explore children

recursively explore all child nodes to find words

Output

Autocomplete results for "ca": [cat car cars]

Complexity Analysis

Time: O(m + k) where m is length of prefix and k is total letters in matched words because we traverse prefix then collect all matches

Space: O(n) where n is total letters in all inserted words for trie storage

vs Alternative: Compared to scanning all words for prefix (O(n * m)), trie is faster for large word sets by sharing prefixes

Edge Cases

Empty prefix string

Returns all words in trie since prefix is empty

DSA Go

if node == nil {
	return results // no words found
}

Prefix not in trie

Returns empty list because no words match

DSA Go

if node == nil {
	return results // no words found
}

Words with shared prefixes

Trie shares nodes for common prefixes, saving space and time

DSA Go

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

When to Use This Pattern

When you need to quickly find all words starting with a prefix, use a trie because it organizes words by shared prefixes for fast lookup.

Common Mistakes

Mistake: Not marking the end of a word, causing incomplete matches
Fix: Always set isEnd = true at the last node of inserted word

Mistake: Not checking if prefix node exists before collecting words
Fix: Return empty list if searchNode returns nil for prefix

Summary

Stores words by shared prefixes to quickly find all words starting with a given prefix.

Use when you want fast autocomplete or prefix search among many words.

The key is to follow prefix nodes then collect all descendant words efficiently.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To encrypt the stored words

B. To sort words alphabetically

C. To efficiently store and search prefixes of words

D. To count the total number of words

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie is a tree-like data structure that stores characters of words in a way that common prefixes share nodes.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires quick lookup of words starting with a given prefix, which Trie supports efficiently.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option C

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie stores prefixes for fast autocomplete lookup [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with encryption methods
• Assuming Trie counts total words only

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

easy

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

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

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

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

Solution

1. Step 1: Identify correct data types for TrieNode fields

   Children should map characters (rune) to child nodes (pointer to TrieNode). isEnd should be a boolean indicating word end.

2. Step 2: Match with given options

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } uses map[rune]*TrieNode and bool for isEnd, which is correct for Trie implementation in Go.

3. Final Answer:

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

4. Quick Check:

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

Hint: Children map keys are runes, values are pointers to TrieNode [OK]

Common Mistakes:

• Using slices instead of maps for children
• Using incorrect types like int or string for isEnd
• Mapping children with wrong key or value types

3. What will be the output of the following Go code snippet that inserts words into a Trie and searches for prefix "app"?

trie := NewTrie()
trie.Insert("apple")
trie.Insert("app")
trie.Insert("application")
results := trie.SearchPrefix("app")
fmt.Println(results)

Assuming SearchPrefix returns all words starting with the prefix.

medium

A. []

B. ["apple", "application"]

C. ["app"]

D. ["app", "apple", "application"]

Solution

1. Step 1: Insert words into Trie

   Words "apple", "app", and "application" are inserted, all sharing prefix "app".

2. Step 2: Search for prefix "app"

   SearchPrefix returns all words starting with "app", so it returns all three inserted words.

3. Final Answer:

   ["app", "apple", "application"] -> Option D

4. Quick Check:

   All words with prefix "app" returned [OK]

Hint: SearchPrefix returns all words starting with given prefix [OK]

Common Mistakes:

• Returning only exact prefix word
• Missing some words sharing prefix
• Returning empty list incorrectly

4. Identify the bug in this Go code snippet for inserting a word into a Trie:

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

medium

A. isEnd should be set to true after insertion

B. children map is not initialized

C. Loop variable ch should be int, not rune

D. Function should return a value

Solution

1. Step 1: Review isEnd assignment after insertion

   After inserting a word, isEnd should mark the node as end of a word, so it must be set to true.

2. Step 2: Check other parts of code

   children map initialization and loop variable type are correct; function does not need to return a value.

3. Final Answer:

   isEnd should be set to true after insertion -> Option A

4. Quick Check:

   isEnd = true after insert [OK]

Hint: Set isEnd true to mark word end [OK]

Common Mistakes:

• Setting isEnd to false instead of true
• Not initializing children map before use
• Expecting Insert to return a value

5. Given a Trie storing words, how can you modify the autocomplete system to return suggestions sorted by frequency of word usage?

hard

A. Store a frequency count at each end node and sort results by this count

B. Sort all words alphabetically before insertion

C. Use a separate array to store frequencies unrelated to Trie

D. Ignore frequency and return words in insertion order

Solution

1. Step 1: Add frequency tracking in Trie nodes

   Modify Trie nodes to store frequency count at nodes marking word ends to track usage.

2. Step 2: Sort autocomplete results by frequency

   When returning suggestions, sort collected words by their stored frequency counts to prioritize popular words.

3. Final Answer:

   Store a frequency count at each end node and sort results by this count -> Option A

4. Quick Check:

   Frequency count in Trie nodes enables sorted suggestions [OK]

Hint: Track frequency in nodes, sort suggestions by count [OK]

Common Mistakes:

• Sorting words before insertion does not help frequency
• Using unrelated arrays breaks Trie efficiency
• Ignoring frequency loses popular word priority