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".