Word Search in Trie in DSA Python - Execution Trace

Concept Flow - Word Search in Trie

Start at root node

↓

For each letter in word

↓

Check if letter child exists?

No→Word NOT found

Yes↓

Move to letter child node

↓

Repeat for next letter

↓

After last letter, check end-of-word flag

↓

Word FOUND

↓

Word NOT found

The search starts at the root and moves through child nodes for each letter. If any letter is missing, the word is not found. At the end, it checks if the node marks a complete word.

Execution Sample

DSA Python

def search_word(root, word):
    node = root
    for letter in word:
        if letter not in node.children:
            return False
        node = node.children[letter]
    return node.is_end_of_word

This code checks if a word exists in the trie by following nodes for each letter and verifying the end-of-word flag.

Execution Table

Step	Operation	Current Node Letter	Letter Checked	Child Exists?	Move To Node	Word Found So Far	Visual State
1	Start at root	'' (root)	h	Yes	Node 'h'	''	root -> h
2	Check letter	h	e	Yes	Node 'e'	h	root -> h -> e
3	Check letter	e	l	Yes	Node 'l'	he	root -> h -> e -> l
4	Check letter	l	l	Yes	Node 'l'	hel	root -> h -> e -> l -> l
5	Check letter	l	o	Yes	Node 'o'	hell	root -> h -> e -> l -> l -> o
6	Check end-of-word	o	-	-	-	hello	root -> h -> e -> l -> l -> o (end)
7	Result	-	-	-	-	Word FOUND	root -> h -> e -> l -> l -> o (end)

💡 Search ends after checking all letters and confirming end-of-word flag at last node.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
node	root	Node 'h'	Node 'e'	Node 'l'	Node 'l'	Node 'o'	Node 'o'	Node 'o'
letter	-	h	e	l	l	o	-	-
word_found_so_far	''	''	h	he	hel	hell	hello	hello

Key Moments - 3 Insights

Why do we check if the child node exists before moving?

Because if the child node for a letter does not exist, it means the word is not in the trie, so we stop searching immediately.

Why do we check the end-of-word flag after the last letter?

Because a path may exist for the letters but not mark a complete word (execution_table step 6). The flag confirms the word ends here.

What happens if the word is empty?

The search starts and ends at the root node. Since no letters are checked, the result depends on whether the root marks an end-of-word, usually False.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node letter at step 4?

A Node 'l'

B Node 'h'

C Node 'e'

D Node 'o'

💡 Hint

Check the 'Current Node Letter' column at step 4 in the execution_table.

At which step does the search confirm the word is found?

A Step 5

B Step 6

C Step 7

D Step 3

💡 Hint

Look for the row where 'Result' operation shows 'Word FOUND' in the execution_table.

If the letter 'o' was missing from the last node, what would happen?

A The search would return True anyway

B The search would stop at step 5 and return False

C The search would continue to next letter

D The search would restart from root

💡 Hint

Refer to the 'Child Exists?' column in execution_table step 5 and the flow in concept_flow.

Concept Snapshot

Word Search in Trie:
- Start at root node
- For each letter, move to child node if exists
- If missing child, word not found
- After last letter, check end-of-word flag
- Return True if flag set, else False

Full Transcript

This visual trace shows how to search a word in a trie data structure. We start at the root node and check each letter of the word in order. If the child node for a letter exists, we move to it. If any letter's child node is missing, the search stops and the word is not found. After checking all letters, we verify if the last node marks the end of a word. If yes, the word exists in the trie; otherwise, it does not. The execution table tracks each step, the current node, letter checked, and the visual state of the trie traversal. Variable tracking shows how the current node and letters change during the search. Key moments clarify common confusions about child node checks and end-of-word flags. The quiz tests understanding of node positions and search outcomes.

Practice

1. What is the main purpose of using a Trie data structure in word search problems?

easy

A. To store words in a way that allows fast prefix-based search

B. To sort words alphabetically

C. To store words in a linked list

D. To compress words into a single string

Solution

1. Step 1: Understand the Trie structure

   A Trie stores characters of words in a tree-like structure where each node represents a character.

2. Step 2: Identify the main use in word search

   This structure allows quick lookup of words by their prefixes, making prefix-based search very efficient.

3. Final Answer:

   To store words in a way that allows fast prefix-based search -> Option A

4. Quick Check:

   Trie = fast prefix search [OK]

Hint: Trie is all about prefix search speed [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie stores words as linked lists
• Assuming Trie compresses words into strings

2. Which of the following is the correct way to check if a character ch exists as a child node in a Trie node's children dictionary named children?

easy

A. if ch in children.keys():

B. if children.has_key(ch):

C. if ch in children:

D. if children.contains(ch):

Solution

1. Step 1: Recall Python dictionary membership check

   In Python, to check if a key exists in a dictionary, use key in dict.

2. Step 2: Identify the correct syntax

   if ch in children: is the correct and most Pythonic way to check key existence.

3. Final Answer:

   if ch in children: -> Option C

4. Quick Check:

   Python dict key check = 'in' keyword [OK]

Hint: Use 'in' keyword to check dict keys in Python [OK]

Common Mistakes:

• Using deprecated has_key() method
• Checking keys() explicitly which is slower
• Using non-existent contains() method

3. Consider the following Python code snippet for searching a word in a Trie:

def search_word(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return node.is_end_of_word

# Trie nodes and root are properly initialized
result = search_word(root, 'cat')

If the Trie contains the words ['car', 'cat', 'cap'], what will be the value of result?

medium

A. None

B. False

C. KeyError

D. True

Solution

1. Step 1: Trace the search for 'cat'

   The function checks each character 'c', 'a', 't' in the Trie nodes. Since 'cat' is inserted, all characters exist and the last node marks end of word.

2. Step 2: Return the end of word flag

   Because 'cat' is a complete word in the Trie, node.is_end_of_word is True, so the function returns True.

3. Final Answer:

   True -> Option D

4. Quick Check:

   Word 'cat' found = True [OK]

Hint: If all chars found and end flag True, return True [OK]

Common Mistakes:

• Returning True without checking end_of_word flag
• Assuming partial prefix means word exists
• Confusing missing character with KeyError

4. The following code tries to search a word in a Trie but raises an error. Identify the bug:

def search_word(root, word):
    node = root
    for ch in word:
        if ch not in node:
            return False
        node = node[ch]
    return node.is_end_of_word

medium

A. Should use 'node.children[ch]' instead of 'node[ch]'

B. Both B and C are correct

C. Should check 'ch not in node.children' instead of 'ch not in node'

D. No bug, code is correct

Solution

1. Step 1: Analyze membership check

   The code checks if ch not in node, but node is an object, not a dictionary. It should check node.children.

2. Step 2: Analyze node traversal

   Similarly, node = node[ch] is incorrect; it should be node = node.children[ch] to access the child node.

3. Final Answer:

   Both B and C are correct -> Option B

4. Quick Check:

   Access children dict properly = Both fixes needed [OK]

Hint: Always access children dict, not node directly [OK]

Common Mistakes:

• Checking keys on node object instead of children dict
• Assigning node = node[ch] instead of node.children[ch]
• Ignoring attribute errors from wrong access

5. You want to find if any word in a Trie starts with a given prefix prefix. Which modification to the standard word search function below will correctly check for prefix existence?

def starts_with(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.children:
            return False
        node = node.children[ch]
    # What to return here?

hard

A. Return True immediately after loop ends

B. Return node.is_end_of_word

C. Return False if node has no children

D. Return True only if prefix length is 1

Solution

1. Step 1: Understand prefix search logic

   To check if any word starts with the prefix, we only need to confirm all prefix characters exist in the Trie.

2. Step 2: Decide return value after loop

   If all characters are found, return True immediately. We do not need to check if the node marks end of a word.

3. Final Answer:

   Return True immediately after loop ends -> Option A

4. Quick Check:

   Prefix found = True [OK]

Hint: If prefix chars found, return True regardless of word end [OK]

Common Mistakes:

• Returning is_end_of_word which fails for prefixes not full words
• Checking children existence unnecessarily
• Restricting prefix length to 1