Count Words with Given Prefix in DSA Go - Execution Trace

Concept Flow - Count Words with Given Prefix

Start at root node

↓

For each character in prefix

↓

Check if character exists in children

↓

Move to child

↓

Repeat for next char

↓

Count words from current node

↓

Return count

Start from the root of the trie, follow each character of the prefix. If all characters exist, count words below the last node.

Execution Sample

DSA Go

func countWordsWithPrefix(root *TrieNode, prefix string) int {
    node := root
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return 0
        }
        node = node.children[ch]
    }
    return countWords(node)
}

This code finds the node matching the prefix and counts all words under it.

Execution Table

Step	Operation	Current Character	Node Visited	Pointer Changes	Visual State
1	Start at root	-	root	node = root	root
2	Check prefix char 'c'	c	root	node = root.children['c']	root -> c
3	Check prefix char 'a'	a	c	node = c.children['a']	root -> c -> a
4	Check prefix char 't'	t	a	node = a.children['t']	root -> c -> a -> t
5	Prefix found, count words	-	t	countWords(t)	root -> c -> a -> t (count words)
6	Count word at 't' node	-	t	-	1 word found ("cat")
7	Count word at 't' children	-	t.children	-	No children with words
8	Return total count	-	t	-	Total words with prefix "cat": 1
9	End	-	-	-	Execution complete

💡 All prefix characters found, counted words under last node.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
node	root	root.children['c']	c.children['a']	a.children['t']	t	t
current character	-	'c'	'a'	't'	-	-
count	0	0	0	0	1	1

Key Moments - 3 Insights

Why do we return 0 if a prefix character is missing?

Because if any character in the prefix is missing in the trie (see Step 2-4 in execution_table), no word can have that prefix.

How do we count words under the prefix node?

We recursively count all words that end at the current node and its children (see Step 5-7).

Why do we move the 'node' pointer at each prefix character?

To follow the path of the prefix in the trie, ensuring we reach the node representing the prefix end (see pointer changes in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the node visited at Step 3?

A root

B c

C a

D t

💡 Hint

Check the 'Node Visited' column at Step 3 in execution_table.

At which step does the code confirm the prefix is fully found?

A Step 6

B Step 4

C Step 5

D Step 7

💡 Hint

Look for the step where counting words starts after prefix traversal.

If the prefix was 'car' instead of 'cat', what would happen at Step 4?

A return 0 because 'r' child missing

B node moves to 't' child

C node moves to 'r' child

D countWords called immediately

💡 Hint

Refer to the condition where prefix character is missing in execution_table Steps 2-4.

Concept Snapshot

Count Words with Given Prefix in Trie:
- Start at root node
- For each prefix char, move to child node
- If missing char, return 0
- After prefix, count all words below
- Counting includes current node if word ends here
- Returns total words with that prefix

Full Transcript

To count words with a given prefix in a trie, start at the root node. For each character in the prefix, check if the character exists among the current node's children. If it does, move the pointer to that child node. If any character is missing, return zero immediately because no words have that prefix. Once all prefix characters are found, count all words that end at or below the current node. This count includes the current node if it marks the end of a word. The final count is the number of words with the given prefix.