Prefix Search Using Trie in DSA Go - Build from Scratch

Prefix Search Using Trie

📖 Scenario: Imagine you are building a simple search feature for a phone contacts app. When a user types some letters, the app should quickly find all contacts whose names start with those letters.

🎯 Goal: Build a Trie data structure to store contact names and implement a prefix search to find all contacts starting with a given prefix.

📋 What You'll Learn

Create a Trie node structure with children and end-of-word marker

Insert given contact names into the Trie

Implement a function to search for all contacts starting with a given prefix

Print the list of contacts found for the prefix

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words starting with a prefix.

💼 Career

Understanding Tries helps in roles involving search optimization, text processing, and building efficient data retrieval systems.

1

Create Trie Node Structure and Insert Contacts

Create a struct called TrieNode with a field children as a map from rune to *TrieNode and a boolean field isEnd. Then create a struct called Trie with a field root of type *TrieNode. Finally, create a function Insert with receiver t *Trie that takes a string word and inserts it into the Trie. Insert these exact contact names: "alice", "bob", "alex", "albert", "bobby".

DSA Go

// Define TrieNode and Trie structs
// Implement Insert method for Trie
// Insert contacts "alice", "bob", "alex", "albert", "bobby"
// Your code here

Hint

Use a map[rune]*TrieNode to store children nodes. Mark the end of a word with a boolean.

2

Add Prefix Search Helper Function

Add a method searchNode with receiver t *Trie that takes a string prefix and returns the *TrieNode where the prefix ends or nil if prefix is not found.

DSA Go

package main

import "fmt"

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

type Trie struct {
	root *TrieNode
}

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

func NewTrie() *Trie {
	return &Trie{root: NewTrieNode()}
}

func (t *Trie) Insert(word string) {
	current := t.root
	for _, ch := range word {
		if _, ok := current.children[ch]; !ok {
			current.children[ch] = NewTrieNode()
		}
		current = current.children[ch]
	}
	current.isEnd = true
}

func main() {
	trie := NewTrie()
	trie.Insert("alice")
	trie.Insert("bob")
	trie.Insert("alex")
	trie.Insert("albert")
	trie.Insert("bobby")
}

// Add searchNode method below
// Your code here

Hint

Traverse the Trie following each character of the prefix. Return nil if any character is missing.

3

Implement Prefix Search to Collect All Words

Add a method collectWords with receiver t *Trie that takes a *TrieNode, a string prefix, and a pointer to a slice of strings results. It should recursively collect all words starting from the node by appending full words to *results. Then add a method StartsWith with receiver t *Trie that takes a string prefix and returns a slice of strings of all words starting with that prefix using searchNode and collectWords.

DSA Go

package main

import "fmt"

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

type Trie struct {
	root *TrieNode
}

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

func NewTrie() *Trie {
	return &Trie{root: NewTrieNode()}
}

func (t *Trie) Insert(word string) {
	current := t.root
	for _, ch := range word {
		if _, ok := current.children[ch]; !ok {
			current.children[ch] = NewTrieNode()
		}
		current = current.children[ch]
	}
	current.isEnd = true
}

func (t *Trie) searchNode(prefix string) *TrieNode {
	current := t.root
	for _, ch := range prefix {
		if _, ok := current.children[ch]; !ok {
			return nil
		}
		current = current.children[ch]
	}
	return current
}

func main() {
	trie := NewTrie()
	trie.Insert("alice")
	trie.Insert("bob")
	trie.Insert("alex")
	trie.Insert("albert")
	trie.Insert("bobby")
}

// Add collectWords and StartsWith methods below
// Your code here

Hint

Use recursion to explore all children nodes and collect words. Use searchNode to find the prefix node first.

4

Print Contacts Matching a Prefix

In main, call StartsWith on the prefix "al" and print the returned slice of strings.

DSA Go

package main

import "fmt"

// ... previous code ...

func main() {
	trie := NewTrie()
	trie.Insert("alice")
	trie.Insert("bob")
	trie.Insert("alex")
	trie.Insert("albert")
	trie.Insert("bobby")

	// Call StartsWith with "al" and print the result
	// Your code here
}

Hint

Call StartsWith("al") and print the returned slice using fmt.Println.