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.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To sort words alphabetically

B. To efficiently find all words that start with a given prefix

C. To store numbers in sorted order

D. To perform arithmetic operations quickly

Solution

1. Step 1: Understand what prefix search means

   Prefix search means finding all words that begin with a certain starting sequence of letters.

2. Step 2: Understand Trie's role in prefix search

   A Trie stores words in a tree-like structure where each node represents a character, making it fast to find all words sharing a prefix.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option B

4. Quick Check:

   Prefix search = efficient word lookup [OK]

Hint: Trie nodes represent characters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting data structures
• Thinking Trie is for arithmetic operations
• Assuming Trie stores numbers only

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

easy

A. type TrieNode struct { value int; left *TrieNode; right *TrieNode }

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

C. type TrieNode struct { data string; next *TrieNode }

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

Solution

1. Step 1: Identify the Trie node components

   A Trie node should have a map from characters (rune) to child nodes and a boolean to mark word end.

2. Step 2: Match the correct Go struct syntax

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } uses a map[rune]*TrieNode and a bool isEnd, which fits the Trie node definition.

3. Final Answer:

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

4. Quick Check:

   Trie node = map + bool [OK]

Hint: Trie nodes use map[rune]*TrieNode and bool isEnd [OK]

Common Mistakes:

• Using slice of int instead of map for children
• Confusing linked list node with Trie node
• Using int instead of bool for isEnd

3. Given the following Go code snippet for inserting words into a Trie and searching for prefix "app":

trie := NewTrie()
trie.Insert("apple")
trie.Insert("app")
trie.Insert("application")
result := trie.StartsWith("app")
fmt.Println(result)

What will be the output of fmt.Println(result)?

medium

A. [app]

B. [apple application]

C. [apple app application]

D. []

Solution

1. Step 1: Insert words into the Trie

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

2. Step 2: Search for prefix "app"

   The StartsWith method returns all words starting with "app", which includes all three inserted words.

3. Final Answer:

   [apple app application] -> Option C

4. Quick Check:

   All words with prefix "app" = [apple app application] [OK]

Hint: StartsWith returns all words sharing the prefix [OK]

Common Mistakes:

• Missing the exact prefix word "app" in results
• Returning only one matching word
• Returning empty list if prefix matches

4. Consider this buggy Go code snippet for searching a prefix in a Trie:

func (t *Trie) StartsWith(prefix string) []string {
    node := t.root
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return nil
        }
        node = node.children[ch]
    }
    return node.words
}

What is the main bug causing incorrect prefix search results?

medium

A. The code does not collect all words under the prefix node

B. The code does not check if node.words is initialized

C. The code returns nil instead of empty slice when prefix not found

D. The code uses wrong variable name for children map

Solution

1. Step 1: Analyze the prefix traversal loop

   The loop correctly moves node down the Trie for each character in prefix.

2. Step 2: Check the return statement after traversal

   Returning node.words assumes all words under prefix are stored there, but usually words are stored in leaf nodes, so it misses collecting all words under subtree.

3. Final Answer:

   The code does not collect all words under the prefix node -> Option A

4. Quick Check:

   Prefix search must gather all subtree words [OK]

Hint: Collect all subtree words after prefix node for correct results [OK]

Common Mistakes:

• Returning nil instead of empty slice is minor, not main bug
• Assuming words stored only at prefix node
• Ignoring recursive collection of words

5. You want to implement a prefix search that returns only words starting with a prefix but excludes words that are exactly the prefix itself. Which modification to the Trie search logic achieves this?

hard

A. After finding prefix node, return all words except the one equal to prefix

B. Return only words that have prefix length or fewer characters

C. Skip marking isEnd for prefix nodes during insertion

D. Return all words including prefix itself

Solution

1. Step 1: Understand the requirement

   We want all words starting with prefix but exclude the word exactly equal to prefix.

2. Step 2: Modify search result filtering

   After collecting all words under prefix node, filter out the word that matches prefix exactly before returning.

3. Final Answer:

   After finding prefix node, return all words except the one equal to prefix -> Option A

4. Quick Check:

   Filter out exact prefix word from results [OK]

Hint: Filter out exact prefix word after collecting all matches [OK]

Common Mistakes:

• Removing isEnd flag breaks normal word insertion
• Returning only longer words by length may miss valid words
• Returning prefix itself defeats the requirement