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.