Prefix Search Using Trie in DSA Go - Execution Trace

Concept Flow - Prefix Search Using Trie

Start at root node

↓

For each character in prefix

↓

Check if character exists in current node's children

↓

Move to child

↓

Repeat for next character

↓

Prefix found

↓

Return all words from this node's subtree

Start from the root and follow each prefix character down the trie. If all characters match, collect all words below.

Execution Sample

DSA Go

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

func (t *TrieNode) SearchPrefix(prefix string) bool {
  node := t
  for _, ch := range prefix {
    if node.children == nil || node.children[ch] == nil {
      return false
    }
    node = node.children[ch]
  }
  return true
}

This code checks if a prefix exists in the trie by traversing nodes for each character.

Execution Table

Step	Operation	Current Character	Node Children Keys	Pointer Changes	Visual State
1	Start at root	-	a, b, c	current = root	root -> {a,b,c}
2	Check 'b' in children	b	a, b, c	current = node for 'b'	root -> b -> {...}
3	Check 'a' in children	a	a, r	current = node for 'a'	root -> b -> a -> {...}
4	Check 't' in children	t	t	current = node for 't'	root -> b -> a -> t -> {...}
5	Prefix found	-	-	-	Prefix 'bat' exists in trie
6	Collect words from current node	-	-	-	Words: 'bat', 'bath', 'batman'
7	End search	-	-	-	Search complete

💡 Traversal ends when all prefix characters are found or a character is missing.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
current	root	node for 'b'	node for 'a'	node for 't'	node for 't'

Key Moments - 3 Insights

Why do we stop searching if a character is not found in children?

Because if the character is missing, the prefix cannot exist in the trie. See execution_table step 2 where we check children keys.

How do we find all words starting with the prefix after traversal?

After reaching the last prefix node, we explore all child nodes recursively to collect words. Refer to execution_table step 6.

Why do we keep updating the 'current' pointer during traversal?

To move down the trie nodes matching each prefix character. This is shown in variable_tracker where 'current' changes each step.

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'current' node after checking character 'a'?

A node for 'b'

B node for 't'

C node for 'a'

D root

💡 Hint

Check variable_tracker column 'After Step 3' for 'current' value.

At which step does the prefix search confirm the prefix exists?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at execution_table row where 'Prefix found' is noted.

If the prefix was 'batman', which step would fail if 'm' was missing in children?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

The failure happens when a character is not found; see step 5 where prefix is confirmed.

Concept Snapshot

Prefix Search Using Trie:
- Start at root node
- For each prefix character, move to child node
- If child missing, prefix not found
- If all found, prefix exists
- Collect all words from last node's subtree

Full Transcript

Prefix search in a trie starts at the root node. For each character in the prefix, we check if it exists in the current node's children. If yes, we move the pointer to that child node. If any character is missing, the prefix does not exist. When all characters are found, the prefix exists. Then, we collect all words from the subtree rooted at the last node. This process is shown step-by-step in the execution table and variable tracker.

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