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.