Trie Search Operation in DSA Go - Build from Scratch

Trie Search Operation

📖 Scenario: Imagine you are building a simple phone contact search feature. You want to quickly check if a contact name exists in your phonebook using a Trie data structure.

🎯 Goal: You will create a Trie, insert some contact names, and then write a search function to check if a given contact name exists.

📋 What You'll Learn

Create a TrieNode struct with children map and endOfWord boolean

Create a Trie struct with root node

Insert given contact names into the Trie

Implement a search function to find if a contact name exists

Print the search result as true or false

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete features, spell checkers, and contact search in phones.

💼 Career

Understanding Tries helps in building efficient search and retrieval systems, a common task in software engineering.

1

Create TrieNode and Trie structs

Create a struct called TrieNode with a field children of type map[rune]*TrieNode and a boolean field endOfWord. Also create a struct called Trie with a field root of type *TrieNode. Initialize the root in a function called NewTrie.

DSA Go

package main

// Your code here

Hint

Think of children as branches for each letter and endOfWord to mark complete words.

2

Insert contact names into the Trie

Add a method Insert to the Trie struct that takes a string word. For each character in word, traverse or create child nodes in children. Mark the last node's endOfWord as true. Insert these exact contact names: "alice", "bob", "carol".

DSA Go

package main

// Add Insert method to Trie
// Insert "alice", "bob", "carol" into the Trie

// Your code here

Hint

Use a loop to go through each letter and create nodes if missing.

3

Implement search function in Trie

Add a method Search to the Trie struct that takes a string word and returns a boolean. Traverse the Trie nodes for each character in word. If any character is missing, return false. After the loop, return the endOfWord value of the last node.

DSA Go

package main

// Add Search method to Trie

// Your code here

Hint

Check each letter node exists, return false if missing, else return if last node marks end of word.

4

Print search results for given names

In the main function, use the Search method to check if "alice", "bob", "carol", and "dave" exist in the Trie. Print the results as true or false on separate lines in this order.

DSA Go

package main

func main() {
	trie := NewTrie()
	trie.Insert("alice")
	trie.Insert("bob")
	trie.Insert("carol")

	// Print search results for "alice", "bob", "carol", "dave"
	// Your code here
}

Hint

Use println to print the boolean results of each search.