Prefix Search Using Trie in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Result

What is the output of the following Go code that inserts words into a trie and searches for words with prefix "app"?

DSA Go

package main

import (
	"fmt"
)

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

type Trie struct {
	root *TrieNode
}

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

func (t *Trie) Insert(word string) {
	node := t.root
	for _, ch := range word {
		if node.children[ch] == nil {
			node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
		}
		node = node.children[ch]
	}
	node.isEnd = true
}

func (t *Trie) StartsWith(prefix string) []string {
	var results []string
	var dfs func(node *TrieNode, path []rune)

	node := t.root
	for _, ch := range prefix {
		if node.children[ch] == nil {
			return results
		}
		node = node.children[ch]
	}

	dfs = func(node *TrieNode, path []rune) {
		if node.isEnd {
			results = append(results, prefix+string(path))
		}
		for ch, child := range node.children {
			dfs(child, append(path, ch))
		}
	}

	dfs(node, []rune{})
	return results
}

func main() {
	trie := NewTrie()
	words := []string{"apple", "app", "application", "apt", "banana"}
	for _, w := range words {
		trie.Insert(w)
	}
	result := trie.StartsWith("app")
	fmt.Println(result)
}

A ["app", "apple", "application"]

B ["apple", "application"]

C ["app", "apt", "apple", "application"]

D ["app", "apple", "application", "apt"]

💡 Hint

Focus on words that start exactly with the prefix "app".

The code inserts words into a trie and searches for all words starting with "app". The words "app", "apple", and "application" start with "app". "apt" does not start with "app" but with "ap" only, so it is excluded.

🧠 Conceptual

intermediate

Number of Nodes in Trie After Insertions

After inserting the words ["cat", "car", "cart", "dog"] into an empty trie, how many nodes does the trie contain (including the root node)?

A 9

B 8

C 7

D 10

💡 Hint

Count shared prefixes only once.

The root node counts as 1. The words share prefixes: "cat" and "car" share 'c' and 'a'. "cart" extends "car" by one letter. "dog" is separate. Counting nodes: root(1), c(2), a(3), t(4), r(5), t(6), d(7), o(8), g(9).

🔧 Debug

advanced

Identify the Error in Trie Search Function

What error does the following Go code produce when searching for prefix "bat" after inserting words ["bat", "bath", "batman"]?

DSA Go

func (t *Trie) StartsWith(prefix string) []string {
	var results []string
	var dfs func(node *TrieNode, path []rune)

	node := t.root
	for _, ch := range prefix {
		if node.children[ch] == nil {
			return results
		}
		node = node.children[ch]
	}

	dfs = func(node *TrieNode, path []rune) {
		if node.isEnd {
			results = append(results, string(path))
		}
		for ch, child := range node.children {
			dfs(child, append(path, ch))
		}
	}

	dfs(node, []rune{})
	return results
}

A The code returns an empty list even though words exist

B The code causes a runtime panic due to nil pointer dereference

C The returned words miss the prefix "bat" in their output

D The code compiles but returns duplicate words

💡 Hint

Check how the prefix is combined with the path in the DFS function.

The DFS appends only the suffix path to results without adding the prefix. So the returned words are missing the prefix "bat". For example, it returns ["", "h", "man"] instead of ["bat", "bath", "batman"].

🚀 Application

advanced

Find All Words With Prefix "pre"

Given a trie with words ["prefix", "preach", "prevent", "press", "present"], what is the output of searching for prefix "pre"?

A ["preach", "prevent", "press", "present"]

B ["prefix", "preach", "prevent", "press", "present"]

C ["prefix", "prevent", "press", "present"]

D ["prefix", "preach", "press", "present"]

💡 Hint

All words start with "pre" so all should be included.

All given words start with the prefix "pre" so the search returns all of them.

🧠 Conceptual

expert

Trie Memory Efficiency Compared to Hash Map

Why is a trie often more memory efficient than storing all words in a hash map when many words share prefixes?

A Because tries use less memory for storing keys as strings compared to hash maps

B Because tries compress all words into a single string internally

C Because tries avoid storing any characters and only store word counts

D Because tries store shared prefixes only once, reducing duplicate storage

💡 Hint

Think about how common parts of words are stored in tries.

Tries store shared prefixes once, so common parts of words are not duplicated, saving memory compared to storing each word separately in a hash map.

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