Autocomplete System with Trie in DSA Go - Build from Scratch

Autocomplete System with Trie

📖 Scenario: You are building a simple autocomplete system like the ones used in search engines or messaging apps. When a user types a few letters, the system suggests words that start with those letters.To do this efficiently, you will use a Trie data structure, which stores words in a tree-like form where each node represents a letter.

🎯 Goal: Create a Trie to store a list of words, then write a function to find all words in the Trie that start with a given prefix. Finally, print the list of suggested words for a sample prefix.

📋 What You'll Learn

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

Insert given words into the Trie

Write a function to find all words starting with a given prefix

Print the list of autocomplete suggestions for the prefix "app"

💡 Why This Matters

🌍 Real World

Autocomplete systems help users type faster by suggesting words based on what they start typing. Tries are efficient for prefix searches in dictionaries, search engines, and text editors.

💼 Career

Understanding Tries and autocomplete logic is useful for software engineers working on search features, text input interfaces, and performance optimization in applications.

1

Create the TrieNode struct and initialize the root

Define a struct called TrieNode with a field children of type map[rune]*TrieNode and a boolean field isEndOfWord. Then create a variable root of type *TrieNode and initialize it with an empty children map.

DSA Go

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

var root = &TrieNode{children: make(map[rune]*TrieNode)}
// Your code here

Hint

Think of children as branches from each letter node, and isEndOfWord as a flag to mark complete words.

2

Add a list of words and a function to insert them into the Trie

Create a slice of strings called words with these exact words: "apple", "app", "application", "bat", "ball". Then write a function insertWord(word string) that inserts a word into the Trie starting from root.

DSA Go

package main

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

var root = &TrieNode{children: make(map[rune]*TrieNode)}

var words = []string{"apple", "app", "application", "bat", "ball"}

func insertWord(word string) {
    // Your code here
}

func main() {
    // Your code here
}

Hint

Loop through each letter in the word. If the letter branch does not exist, create it. Mark the last letter node as end of word.

3

Write a function to find all words starting with a prefix

Write a function autocomplete(prefix string) []string that returns a slice of strings containing all words in the Trie that start with prefix. Use a helper function dfs(node *TrieNode, path string, results *[]string) to collect words by depth-first search from the prefix node.

DSA Go

package main

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

var root = &TrieNode{children: make(map[rune]*TrieNode)}

var words = []string{"apple", "app", "application", "bat", "ball"}

func insertWord(word string) {
    current := root
    for _, ch := range word {
        if current.children[ch] == nil {
            current.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        current = current.children[ch]
    }
    current.isEndOfWord = true
}

func autocomplete(prefix string) []string {
    // Your code here
}

func dfs(node *TrieNode, path string, results *[]string) {
    // Your code here
}

func main() {
    for _, w := range words {
        insertWord(w)
    }
}

Hint

First find the node matching the prefix. Then explore all child nodes recursively to collect complete words.

4

Print autocomplete suggestions for the prefix "app"

Call the autocomplete function with the prefix "app" and print the returned slice of strings.

DSA Go

package main

// Previous code above

func main() {
    for _, w := range words {
        insertWord(w)
    }
    suggestions := autocomplete("app")
    // Your code here
}

Hint

Use fmt.Println(suggestions) to print the list of words starting with "app".

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