Word Search in Trie in DSA Python

Mental Model

A trie stores words by sharing common prefixes, making it easy to check if a word exists by following letters step-by-step.

Analogy: Imagine a tree of roads where each road sign is a letter. To find a word, you follow the signs letter by letter until you reach the end of the word or get lost.

root
 ↓
 a -> b -> c -> null
 ↓
 t (end)

Each arrow points to the next letter node in the trie.

Dry Run Walkthrough

Input: Insert words: 'cat', 'car', 'bat'. Search for 'car' and 'cap'.

Goal: Check if 'car' and 'cap' exist in the trie after inserting the words.

Step 1: Insert 'cat' letter by letter into the trie

root -> c -> a -> t[end]

Only 'cat' inserted, nodes created for c, a, t with t marked as word end

Why: We build the path for the word 'cat' so it can be found later

Step 2: Insert 'car' letter by letter, sharing prefix with 'cat'

root -> c -> a -> t[end]
                 ↓
                 r[end]

'car' shares c and a nodes, adds r node marked as word end

Why: Sharing prefix saves space and links similar words

Step 3: Insert 'bat' letter by letter, new branch from root

root -> c -> a -> t[end]
                 ↓
                 r[end]

root -> b -> a -> t[end]

New branch for 'bat' created

Why: Words with different first letters start new branches

Step 4: Search for 'car' by following letters c -> a -> r

root -> c -> a -> r[end]

Found 'car' because r node is marked as word end

Why: All letters found and last node marks end of word

Step 5: Search for 'cap' by following letters c -> a -> p

root -> c -> a -> null

'p' node does not exist after 'a', so 'cap' not found

Why: Missing letter means word does not exist in trie

Result:

Trie structure:
root -> c -> a -> t[end]
                 ↓
                 r[end]
root -> b -> a -> t[end]

Search results:
'car' found: True
'cap' found: False

Annotated Code

DSA Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # create node if missing
            node = node.children[char]  # move to next node
        node.is_end_of_word = True  # mark end of word

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False  # letter missing, word not found
            node = node.children[char]  # move to next node
        return node.is_end_of_word  # check if end of word

# Driver code
trie = Trie()
words_to_insert = ['cat', 'car', 'bat']
for w in words_to_insert:
    trie.insert(w)

search_words = ['car', 'cap']
for w in search_words:
    print(f"'{w}' found: {trie.search(w)}")

if char not in node.children: node.children[char] = TrieNode()

create new node if letter path does not exist

node = node.children[char]

advance to next letter node to continue insertion or search

node.is_end_of_word = True

mark current node as end of a valid word after insertion

if char not in node.children: return False

stop search early if letter path missing

return node.is_end_of_word

confirm word exists only if last node marks end of word

Output

'car' found: True

'cap' found: False

Complexity Analysis

Time: O(m) because we process each letter of the word once during insert or search, where m is word length

Space: O(m) for insertion because new nodes are created only for letters not already in the trie

vs Alternative: Compared to searching words in a list (O(n*m)), trie search is faster (O(m)) because it avoids scanning all words

Edge Cases

Search for empty string

Returns False because empty string is not inserted as a word

DSA Python

return node.is_end_of_word

Insert duplicate word

No new nodes created, end_of_word flag remains True, no error

DSA Python

node.is_end_of_word = True

Search for word that is prefix of another word

Returns True only if prefix word was inserted and marked as end

DSA Python

return node.is_end_of_word

When to Use This Pattern

When you need to quickly check if words or prefixes exist in a large set, use a trie because it organizes words by shared prefixes for fast lookup.

Common Mistakes

Mistake: Not marking the end of word node, causing search to return True for prefixes that are not full words
Fix: Set is_end_of_word = True at the last node of inserted word

Mistake: Returning True immediately after finding all letters without checking end of word flag
Fix: Return True only if the last node's is_end_of_word is True

Summary

It stores words letter by letter in a tree structure to quickly check if a word exists.

Use it when you want fast word search or prefix checks among many words.

The key is sharing common prefixes so you only follow letters step-by-step to find words.

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